终于下定决心不碰运气写二分了。。。
思路比较乱，建议直接点进参考①
来说一下我记忆的方法
注意left<=right
首先标准查找是随机的找到一个，分三类，找不到返回-1
然后如果要找第一个和最后一个，因为是准确查找，所以要有判别和找不到返回-1
里面的大于还是大于等于，要具体分析。（分析相等的时候向左找还是向右找，返回谁）
举个例子
寻找最后一个相等的，没有的话找比key小的最后一个（searchLastEqualOrSmaller）
这两个元素的位置都是偏右（比如说{1,2,3,4,4,4,5,6}，分成1,2,3|4,4,4|5,6，3和最后一个4都在所在区间的右边），因此要向右找，让相等的情况跟着缩小左边界，因此是大于
解释一下为什么返回right，根据while结束条件，最后right<right，如果没有相等的，arr[right]<key<arr[left]，否则，key==arr[right]<arr[left]（所以返回left就是比key大的第一个）
大于等于同理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
1 //递增
2 #include<cstdio>
3 #include<iostream>
4 #include<cstring>
5 #include<algorithm>
6 using namespace std;
7 int search(int *arr,int n,int key){
8 int left=0,right=n-1;
9 while(left<=right){
10 int mid=(left+right)>>1;
11 if(arr[mid]==key) return mid;
12 else if(arr[mid]>key) right=mid-1;
13 else left=mid+1;
14 }
15 return -1;
16 }
17 int searchFirstEqual(int *arr,int n,int key){
18 int left=0,right=n-1;
19 while(left<=right){
20 int mid=(left+right)>>1;
21 if(arr[mid]>=key) right=mid-1;
22 else left=mid+1;
23 }
24 if(left<n&&arr[left]==key){
25 return left;
26 }
27 return -1;
28 }
29 int searchLastEqual(int *arr,int n,int key){
30 int left=0,right=n-1;
31 while(left<=right){
32 int mid=(left+right)>>1;
33 if(arr[mid]>key) right=mid-1;
34 else left=mid+1;
35 }
36 if(right>=0&&arr[right]==key){
37 return right;
38 }
39 return -1;
40 }
41 int searchLastEqualOrSmaller(int *arr,int n,int key){
42 int left=0,right=n-1;
43 while(left<=right){
44 int mid=(left+right)>>1;
45 if(arr[mid]>key) right=mid-1;
46 else left=mid+1;
47 }
48 return right;
49 }
50 int searchLastSmaller(int *arr,int n,int key){
51 int left=0,right=n-1;
52 while(left<=right){
53 int mid=(left+right)>>1;
54 if(arr[mid]>=key) right=mid-1;
55 else left=mid+1;
56 }
57 return right;
58 }
59 int searchFirstEqualOrLarger(int *arr,int n,int key){
60 int left=0,right=n-1;
61 while(left<=right){
62 int mid=(left+right)>>1;
63 if(arr[mid]>=key) right=mid-1;
64 else left=mid+1;
65 }
66 return left;
67 }
68 int searchFirstLarger(int *arr,int n,int key){
69 int left=0,right=n-1;
70 while(left<=right){
71 int mid=(left+right)>>1;
72 if(arr[mid]>key) right=mid-1;
73 else left=mid+1;
74 }
75 return left;
76 }
77
78 int main(){
79 int arr[17] = {1,
80 2, 2, 5, 5, 5,
81 5, 5, 5, 5, 5,
82 5, 5, 6, 6, 7};
83 printf("First Equal : %2d \n", searchFirstEqual(arr, 16, 5));
84 printf("Last Equal : %2d \n", searchLastEqual(arr, 16, 5));
85 printf("First Equal or Larger : %2d \n", searchFirstEqualOrLarger(arr, 16, 5));
86 printf("First Larger : %2d \n", searchFirstLarger(arr, 16, 5));
87 printf("Last Equal or Smaller : %2d \n", searchLastEqualOrSmaller(arr, 16, 5));
88 printf("Last Smaller : %2d \n", searchLastSmaller(arr, 16, 5));
89 return 0;
90 return 0;
91 }
View Code
参考：①你真的会写二分查找吗 - luoxn28 - 博客园
②你真的会写二分检索吗？-liubird- ChinaUnix博客（测试段代码来源）