首先想清楚!!二分查找分为四种(数组中包含重复元素)分别为
YES_LEFT ----> 能找到且返回最左边的数的位置
YES_RIGHT ----> 能找到且返回最右边的数的位置
NO_LEFT ----> 不能找到且返回左边与其接近的数的位置
NO_RIGHT ----> 不能找到且返回右边与其接近的数的位置
例如下列数组:
2 3 4 4 4 6 6 6 6 7
YES_LEFT(4) -> 2
YES_RIGHT(4) -> 4
NO_LEFT(6) -> 4
NO_RIGHT(6) -> 9
对于YES_LEFT或者NO_RIGHT
int bSearch(int begin, int end, int e)
{
int mid;
int left = begin;
int right = end;
while(left <= right)
{
mid = (left + right) >> 1;
if(num[mid] >= e){
right = mid - 1;
}else {
left = mid + 1;
}
}
return left;
}
对于YES_RIGHT或者NO_LEFT
int bSearch(int begin, int end, int e)
{
int mid;
int left = begin;
int right = end;
while(left <= right)
{
mid = (left + right) >> 1;
if(num[mid] > e){
right = mid - 1;
}else {
left = mid + 1;
}
}
return right;
}
网友评论