首先想清楚！盾似！二分查找分為四種（數(shù)組中包含重復(fù)元素）分別為
YES_LEFT ----> 能找到且返回最左邊的數(shù)的位置
YES_RIGHT ----> 能找到且返回最右邊的數(shù)的位置
NO_LEFT ----> 不能找到且返回左邊與其接近的數(shù)的位置
NO_RIGHT ----> 不能找到且返回右邊與其接近的數(shù)的位置
例如下列數(shù)組：
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
對(duì)于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;
}
對(duì)于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;
}
