二分查找是分治算法的经典应用，它可以每次把问题的规模减少一半，从而在log的时间内找到结果。
二分查找
二分查找适用于有序数组的查找，它的核心思想是，选取一个数组中间的数字a[mid] 和要查找的数字 target 进行比较，如果target小于中间数字，则可以排除右半部分；如果target大于中间数字，可以排除左半部分。
二分查找的典型代码如下，若查找到，返回对应元素下标，否则返回-1 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
int binSearch(vector<int> & a, int target) { int start = 0; int end = a.size(); while (end - start > 0) { int mid = (start + end) / 2; if (target < a[mid]) end = mid; else if (a[mid] < target) start = mid+1; else return mid; } return -1; } |
旋转数组查找
Search in Rotated Sorted Array | LeetCode OJ
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
这里的旋转数组，其实就是一个升序数组循环右移后形成的，数组的样子大概如下图所示：
虽然整体不是有序的了，但毕竟是从有序变化而来，旋转数组中，左半部分是大于右半部分的，而且两个部分是各自有序的。
可以用二分查找的方法，比较中间元素和目标target 。不同的是，此时我们要考虑中间数字是位于旋转数组的左半部分还是右半部分。
1. target < a[mid] 时，
1.1 如果mid位于旋转数组的左半部分 那么小于a[mid]的元素分布在左右两部分都有（绿色）
而且这两个部分也是有序的，左半部分的大于右半部分。此时需要判断target和左半部分第一个元素，就可以确定target是在左边还是右边。
1.1.1 如果target >= a[start] 则target在左半部分.
1.1.2 如果target < a[start] 则target在右半部分
1.2 如果mid位于旋转数组的右半部分 此时旋转数组中小于a[mid]的元素均位于左侧
2. target > a[mid] 时，情况也是类似的。
代码：
|
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 |
class Solution { public: int search(vector<int>& nums, int target) { int start = 0; int end = nums.size(); while (end - start > 0) { int mid = (start+end) / 2; if (target < nums[mid]) { if (nums[start] < nums[mid] && target < nums[start]) start = mid+1; else end = mid; } else if (nums[mid] < target) { if (nums[start] > nums[mid] && target > nums[end-1]) end = mid; else start = mid+1; } else return mid; } return -1; } }; |
二分查找变种
有重复元素
Search for a Range | LeetCode OJ
iven an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
这个问题可以分解为2个二分查找的问题：当待查找的数字在数组中有多个时，一个版本返回其中最前面的下标，一个版本返回最后面的下标。
先来看第一个版本，我们需要返回数组中大于target的第一个元素的下标。例如：数组[0, 2, 2, 3]，查找-1返回0，查找0返回1，查找1返回1，查找2返回3，查找3返回4，查找4返回4
先上代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int search_after(vector<int> & a, int x) { int low = 0; int high = a.size(); while (low < high) { int mid = (low+high) / 2; if (x < a[mid]) high = mid; else low = mid+1; } return low; } |
可以使用循环不变式来理解这段代码为什么会返回大于target的第一个元素的下标：
下面使用n表示数组a的大小。使用数学中的区间表示，[0, low)表示前闭后开区间，不包括a[low]；[ high, n )是前开后闭区间，包括a[high]
这里的不变式是，数组a中，[0, low)中的元素的值 <=x ；[ high, n )中的元素的值 >x 。
循环开始前，low=0， high=n ，是朴素的空区间的情况，不变式是成立的。即[0,0)中元素<=x 成立，[n,n)的元素>x也成立。
在每一次循环时，有两种情况：
1. 当x<a[mid]时，high=mid 。[ high, n )中的元素的值 >x 仍然成立；
2. else的情况，x>=a[mid]，此时low=mid+1 ，[0, low) 中的元素的值 <=x 仍然成立（也就是区间[0,mid]）。
循环结束后，low==high ，不变式仍成立：[0,low) 中元素<=x ；[low, n)元素 > x 。这时a[low]就是大于x的第一个元素。
再来看返回数组中小于target的最后一个元素的下标的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int search_before(vector<int> & a, int x) { int low = 0; int high = a.size(); while (low < high) { int mid = (low+high) / 2; if (x <= a[mid]) high = mid; else low = mid+1; } return --low; } |
这里的循环不变式是：
[0,low) 中的元素的值 <x
[high,n)中的元素的值 >=x
循环结束后，low是>=x中的元素中的最小的。因此low-1就是<x的元素中的最大的。
Leetcode的代码：
|
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 |
class Solution { public: int search_before(vector<int> & a, int x) { int low = 0; int high = a.size(); while (low < high) { int mid = (low+high) / 2; if (x <= a[mid]) high = mid; else low = mid+1; } return --low; } int search_after(vector<int> & a, int x) { int low = 0; int high = a.size(); while (low < high) { int mid = (low+high) / 2; if (x < a[mid]) high = mid; else low = mid+1; } return low; } vector<int> searchRange(vector<int>& nums, int target) { int lo = search_before(nums, target); int hi = search_after(nums, target); vector<int> v; if (hi - lo <= 1) { v.push_back(-1); v.push_back(-1); return v; } else { v.push_back(lo+1); v.push_back(hi-1); } return v; } }; |
查找插入位置
Search Insert Position | LeetCode OJ
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
这个只要使用上面的search_before的代码，返回大于等于x的第一个元素的下标就可以了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int searchInsert(vector<int>& nums, int target) { vector<int>& a = nums; int x = target; int low = 0; int high = a.size(); while (low < high) { int mid = (low+high) / 2; if (x <= a[mid]) high = mid; else low = mid+1; } return low; } }; |
支付宝打赏 
微信打赏