二分查找

【二分查找】

二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

常规的二分查找：

 1 int binarySearch(int a[],int n,int key)
 2 {
 3     int left = 0;
 4     int right = n-1;
 5     while (left <= right )  //不要忘记等号
 6     {
 7         int mid = (left + right) / 2;
 8         if (a[mid] > key)
 9             right = mid - 1;
10         else if (a[mid] < key)
11             left = mid + 1;
12         else
13             return mid;
14     }
15     return -1;
16 }

这里强调下不要忘记 left <= right 的等号比如a[3] = {1,3,5} 我们需要查找5 如果 letf < right 的话就不会进入while循环，这会导致找不到结果

【变形一】查找第一个与key相等的元素

因为找第一个所以不断往左边找所以等于号加在 right = mid-1

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

【变形二】查找最后一个与key相等的元素

因为找最后一个所以等号加在left = mid + 1

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

【变形三】查找最后一个小于或等于key的元素

小于等于类似等于所以同样加载left = mid + 1

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

【变形四】查找最后一个小于key的元素

小于的话要不断的往左边找所以等号加在right = mid - 1

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

【变形五】查找第一个等于或大于key的元素

等于或大于类似等于等号加在right = mid - 1

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

【变形六】查找第一个大于key的元素

大于要不断往右边找等号加在left = mid + 1

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

变形总结：

如果是找到第一个则都是返回left 如果是最后一个则返回right

如果我们要找第一个 > key 的元素或者元素的下标可以利用　　　　upper_bound 返回第一个大于的元素的下标；

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　int pos = upper_bound(a,a+n,key) - a; (默认数组a从0开始记录)

如果我们要找第一个 >= key 的元素或者元素的下标可以利用　　 lower_bound返回第一个大于等于元素的下标；

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　int pos = lower_bound(a,a+n,key) - a; （默认数组a从0开始记录）