二分法

int bsearch(vector<int>& a, int target){
int lo = 0;
int hi = a.size()-1;
while(l<=r){
int mid = lo + (hi-lo)/2;
if(a[mid] == target){
return mid;
}else if(a[mid] < target){
lo = mid+1;
}else{
hi = mid-1;
}
}
return -1;
}


1. 查找第一个值等于给定值的元素
2. 查找最后一个值等于给定值的元素
3. 查找第一个大于等于给定值的元素
4. 查找最后一个小于等于给定值的元素

二分法的变种

int a[10] = { 1,3,4,5,6,8,8,8,11,18};

index:		  0 1 2 3 4 5 6 7  8  9


int a[10] = { 1,3,4,5,6,8,8,8,11,18};
int index = bsearch(a,8);
while(index>=0 && a[index] == 8){
index--;
}


int bsearch(vector<int>& a, int target){
int lo = 0;
int hi = a.size()-1;
while(l<=r){
int mid = lo + (hi-lo)/2;
if(a[mid] == target){
//增加判断条件
if(mid==0 || a[mid-1] != value){
return mid;
}else{
hi = mid-1;
}
}else if(a[mid] < target){
lo = mid+1;
}else{
hi = mid-1;
}
}
return -1;
}


if(a[mid] == target){
if( mid == a.size()-1 || a[mid+1] != target){
return mid;
}else{
lo = mid+1;
}
}


if(a[mid] >= target){
if(mid==0 || a[mid-1]<target){
return mid;
}else{
hi = mid-1;
}
}else{
lo = mid+1;
}


if(a[mid] <= target){
if(mid==a.size()-1 || a[mid]+1 > target){
return mid;
}else{
lo = mid+1;
}
}else{
hi = mid-1;
}


求解一个正数的平方根

1. 对于任何一个正数，如果它大于1，其平方根的取值范围为 1< s < n/2 (n>=1)。其中s表示平方根，n表示输入的正数。
2. 如果它小于或者等于1，其平方根的取值范围为 0 < n < s <=1

low = 0, high = 1 + n/2
mid = low + (high-low)/2
while(true){
s = mid*mid;
if(s==n){
return mid;
}else if(s > n){
high = mid;
}else {
low = mid;
}
}


const double EPSILON = 0.00001;
double sqrt(double num) {
double l = 0;
double r = num/2+1;
while( l< r){
double mid = l + (r-l)/2;
double s = mid*mid;
double diff = abs(s-num);
//二分终止条件
if(diff < EPSILON){
return mid;
}
if(s < num){
l = mid;
}else{
r = mid;
}
}
return -1;
}


num = 9为例，上述代码执行的过程为: