【二分查找】

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

 

常规的二分查找：

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         else13             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开始记录）