二分法的变式 | Eternal_zttz

二分法的变式

二分虽然看上去简单,写代码感觉上也很简单,然而实际上真的没有那么简单~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//查找key
int search1(int arr[], int n, int key){
int left = 0, right = n-1;
while(left <= right){
int mid = (left+right) / 2;
if(arr[mid] > key)
right = mid - 1;
else if(arr[mid] < key)
left = mid + 1;
else if(arr[mid] == key)
return mid;
}
return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//查找第一个与key相等的元素
int search2(int arr[],int n, int key){
int left = 0, right = n -1;
while(left <= right){
int mid = (left + right) /2;
if(arr[mid] >= key)
right = mid - 1;
else if(arr[mid] < key)
left = mid + 1;
}
if(left < n && arr[left] == key)
return left;
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//查找最后一个与key相等的元素
int search3(int arr[],int n,int key){
int left = 0, right = n -1;
while(left <= right){
int mid = (left + right) / 2;
if(arr[mid] > key)
right = mid - 1;
else
left = mid + 1;
}
if(right >=0 &&arr[right] == key)
return right;
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
//查找第一个大于或等于key的元素
int search4(int arr[], int n, int key){
int left = 0, right = n -1;
while(left <= right){
int mid = (left + right) /2;
if(arr[mid] >= key)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
//查找第一个大于key的元素
int search5(int arr[],int n, int key){
int left = 0, right = n - 1;
while(left <= right){
int mid = (left + right) /2 ;
if(arr[mid] > key)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
//查找最后一个小于等于key的元素
int search6(int arr[], int n, int key){
int left = 0, right = n - 1;
while(left <= right){
int mid = (left + right) / 2;
if(arr[mid] > key)
right = mid -1;
else
left = mid +1;
}
return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
//查找最后一个小于key的元素
int search7(int arr[],int n, int key){
int left = 0 ,right = n -1 ;
while(left <= right){
int mid = (left + right) /2;
if(arr[mid] >= key)
right = mid - 1;
else
left = mid + 1;
}
return right;
}

算法真是博大精深

-------------The End-------------