题解 | #二分查找-II#

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 如果目标值存在返回下标，否则返回 -1 * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector& nums, int target) { // write code here //首先这已经是个有序的数组了即升序排列好了，但是数组中有重复数字，也就是说当你找到目标值 //target但是可能他并不是第一个出现的target，此时应该继续二分并时刻更新下标最小的target出现的下标 int low=0,high=nums.size(),position=-1;//position为记录target的标记位 if(high==0) return position;//即为最后一种特殊情况即数组中一个元素都没有 while(high>=low) { int mid=(high+low)/2;//找出中点位置 if(nums[mid]==target)//若找到先用position记录下来，然后继续缩小查找范围 { position=mid; high=mid-1; } else if(nums[mid]<target)//因为是升序，所以target一定在后半部分里 { low=mid+1; } else{//此时一定在前半部分里 high=mid-1; } } //当while循环结束时，此时的position一定就为target第一次出现的下标 return position; } }; //另外本人真的是个战五渣，就连vector是个啥都是现场百度的，太菜了，所以写的不好轻点喷~