首页 > 代码库 > 二分查找及其落点问题
二分查找及其落点问题
对于传统的二分查找，若能找到，则返回target的下标，若找不到则返回-1后，退出函数。齐代码比较简单，如下：
int bSearch(vec<int> vec, int start,int end,int target){ int first = start,last = end,mid; while(first<=last) { mid = (first + last)>>1; if(vec[mid] == target) return mid; else if(vec[mid] < target) first = mid + 1; else last = mid - 1; } return -1; }
上面的代码在处理一般的查找可满足要求，但是对于一些特殊情形有局限性，如重复的，查找失败后还要插入的....
下面介绍2类二分查找的变形：前提：查找的数target，vec[0]<=target<=vec[end],如果不在下面的性质不成立。且函数的start参数和end参数是数组元素的下标，对于输入vector<int> vec = {1,2,2,4,4,8,10}，start = 0，end = 6;若end = 7，对Yes_Left和No_Right无影响，但是对后面两种情况有影响，特别要注意
输入：vector<int> vec = {1,2,2,4,4,8,10};
查找成功返回最左边的值得下标(Yes_Left),即查找4返回3，或者查找失败，返回数组中恰好大于target的元素的下标(No_Right)，即查找3返回3，这2种情况代码如下：
int bSearch(vector<int> vec,int start,int end,int target){ int mid,left = start,right = end; while(left<=right) { mid = (left + right)>>1; if(vec[mid]>=target) right = mid - 1; else left = mid + 1; } return left;}
还是上面的输入，查找成功返回最右边的值的下标(Yes_Right),即查找4返回4，或者查找失败，返回数组中恰好小于target的元素的下标(No_Left),即查找3返回2，代码如下
int bSearch(vector<int> vec,int start,int end,int target){ int mid,left = start,right=end; while(left<=right) { mid = (left + right)>>1; if(vec[mid]>target)right = mid - 1; else left = mid + 1; } return right;}
感觉碉堡了呀！！
二分查找及其落点问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。