二分查找问题全集
1,原始二分查找
题目:给定一个有序(非降序)数组A,求任意一个i使得A[i]等于target,不存在则返回-1例如:[2,4,6,8,9]找(4) 位置1
1.1 递归版
[cpp]view plain copy
print?
1.int bSearch(int a[], int low, int high, int target){
2. if(low > high)
3. return -1;
4.int mid = (low + high)/2;
5. if(target
a[mid])
8. return bSearch(a,mid+1,high,target);
9. //if(target == a[mid])
10. return mid;
11.}
1.2 迭代版
[cpp]view plain copy
print?
1.int search(int A[], int n, int target)
2.{
3.int low = 0, high = n-1;
4. while(low <= high)
5. {
6. // 注意:若使用(low+high)/2求中间位置容易溢出
7.int mid = low+((high-low)>>1);
8. if(A[mid] == target)
9. return mid;
10. else if(A[mid] < target)
11. low = mid+1;
12. else // A[mid] > target
13. high = mid-1;
14. }
15. return -1;
16.}
1.3 返回插入位置
给定一个有序(非降序)数组A,若target在数组中出现,返回位置,若不存在,返回它应该插入的位置。
[cpp]view plain copy
print?
1.int search(int A[], int n, int target)
2.{
3.int low = 0, high = n-1;
4. while(low <= high)
5. {
6. // 注意:若使用(low+high)/2求中间位置容易溢出
7.int mid = low+((high-low)>>1);
8. if(A[mid] == target)
9. return mid;
10. else if(A[mid] < target)
11. low = mid+1;
12. else // A[mid] > target
13. high = mid-1;
14. }
15. return -(low+1);
16.}
之所以返回-(low+1)而不是直接返回-low是因为low可能为0,如果直接返回-low就无法判断是正常返回位置0还是查找不成功返回的0。
2,含重复元素,求=target的最小一个
问题:给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]等于target,不存在则返回-1
例如:A[2,4,6,8,8,8,9]求8得最小位置3
[cpp]view plain copy
print?
1.int search(int A[], int n, int target)
2.{
3.int low = 0, high = n-1;
4. while(low <= high)
5. {
6. // 注意:若使用(low+high)/2求中间位置容易溢出
7.int mid = low+((high-low)>>1);
8. if(A[mid] == target)
9. {
10. if(mid > 0 && A[mid-1] == target)
11. high = mid-1;
12. else
13. return mid;
14. }
15. else if(A[mid] < target)
16. low = mid+1;
17. else // A[mid] > target
18. high = mid-1;
19. }
20. return -(low+1);
21.}
3,含重复元素,求=target的最大一个
问题:给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]等于target,不存在则返回-1
例如:A[2,4,6,8,8,8,9]求8得最大位置5
[cpp]view plain copy
print?
1.int search(int A[], int n, int target)
2.{
3.int low = 0, high = n-1;
4. while(low <= high)
5. {
6. // 注意:若使用(low+high)/2求中间位置容易溢出
7.int mid = low+((high-low)>>1);
8. if(A[mid] == target)
9. {
10. if(mid < n-1 && A[mid+1] == target)
11. low = mid+1;
12. else
13. return mid;
14. }
15. else if(A[mid] < target)
16. low = mid+1;
17. else // A[mid] > target
18. high = mid-1;
19. }
20. return -(low+1);
21.}
4,含重复元素,求>1);
8. if(A[mid] == target)
9. {
10. if(mid > 0 && A[mid-1] == target)
11. high = mid-1;
12. else
13. return (mid==0)?-1:mid-1;
14. }
15. else if(A[mid] < target)
16. low = mid+1;
17. else // A[mid] > target
18. high = mid-1;
19. }
20. return -(low+1);
21.}
5,含重复元素,求>target的最小一个
问题:给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A[i]大于target,不存在则返回-1
例如:A[2,4,6,8,8,8,9]求6的最小位置3
问题转化:含重复元素,求3【=target的最大一个】的后一个。
[cpp]view plain copy
print?
1.int search(int A[], int n, int target)
2.{
3.int low = 0, high = n-1;
继续阅读
浙公网安备 33021202002483