「手撕算法」锁定大厂看这就可

这里主要是看看原始数组有重复数的情况。

二分

1 查找第一个值等于给定值的情况(查找元素7)

·

首先7与中间值a[4]比较，发现小于7，于是在5到9中继续查找，中间a[7]=7,但是这个数7不是第一次出现的。那么我们检查这个值的前面是不是等于7，如果等于7，说明目前这个值不是第一次出现的7，此时更新rihgt=mid-1。ok我们看看代码

int BinarySerach(vector& nums, int n,int target) {     int left = 0, right = n-1;     while (left <= right) {         int mid = left+((right-left)>>1);         if (nums[mid]>value)         {             right=mid-1;         } else if(nums[mid]<value)         {             left=mid+1;         }else         {             if((mid==0)||(nums[mid-1]!=value))             {                 return mid;             }else             {                 left=mid-1;             }         }     return -1; } 

2 查找最后一个值等于给定值的情况

假设nums[mid]这个值已经是最后一个元素了，那么它肯定是要找到最后一个值。如果nums[mid]的下一个不等于value，那说明nums[mid]就是我们需要找到最后一个等于给定值的值。

int BinarySerach(vector& nums, int n,int target) {     int left = 0, right = n-1;     while (left <= right) {         int mid = left+((right-left)>>1);         if (nums[mid]>value)         {             right=mid-1;         } else if(nums[mid]<value)         {             left=mid+1;         }else         {             if((mid==n-1)||(nums[mid+1]!=value))             {                 return mid;             }else             {                 left=mid+1;             }         }     return -1; } 

3 查找第一个大于等于给定值的情况

如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1 如果nums[mid]大于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。相反 如果nums[mid-1]也是大于等于查找的值，那么说明查找的元素在[left,mid-1]之间，所以我们需要将right更新为mid-1 int BinarySerach(vector& nums, int n,int target) {     int left = 0, right = n-1;     while (left <= right) {         int mid = left+((right-left)>>1);         if (nums[mid]>value)         {             right=mid-1;         } else if(nums[mid]<value)         {             left=mid+1;         }else         {             if((mid==n-1)||(nums[mid+1]!=value))             {                 return mid;             }else             {                 left=mid+1;             }         }     return -1; } 

4 查找第一个大于等于给定值的情况

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!