二分查找

终于下定决心不碰运气写二分了。。。

思路比较乱，建议直接点进参考①

来说一下我记忆的方法

注意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 #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 
", searchFirstEqual(arr, 16, 5));
84     printf("Last Equal            : %2d 
", searchLastEqual(arr, 16, 5));
85     printf("First Equal or Larger : %2d 
", searchFirstEqualOrLarger(arr, 16, 5));
86     printf("First Larger          : %2d 
", searchFirstLarger(arr, 16, 5));
87     printf("Last Equal or Smaller : %2d 
", searchLastEqualOrSmaller(arr, 16, 5));
88     printf("Last Smaller          : %2d 
", searchLastSmaller(arr, 16, 5));
89     return 0;
90     return 0;
91 }

View Code

参考：①你真的会写二分查找吗 - luoxn28 - 博客园

　　　②你真的会写二分检索吗？-liubird-ChinaUnix博客（测试段代码来源）