二分搜索定义
二分搜索算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程中从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较，如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
复杂度分析
最坏时间复杂度O（logn）
最好时间复杂度O（1）
平均时间复杂度O（logn）
空间复杂度：迭代O（1）、递归O（logn）（尾递归、可改写成循环）。
基本算法
这是二分搜索算法的基本算法。
1、闭区间：[left, right]
2、中位数：mid = low + (high - low) / 2;
3、递归终止条件：low > high;
4、返回值：low;
二分搜索的过程就是一个维护low的过程。
low从0开始，只有在中位数遇到确定小于目标数时才前进，且永不后退。low一直在朝着第一个目标值的位置在逼近，直到最终到达。
要求数组中没有重复的元素。
// 迭代 int binary_search(vector<int>& nums, int target) { int low = 0, high = nums.size() - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] > target) low = mid + 1; if (nums[mid] < target) high = mid - 1; if (nums[mid] == target) return mid; } return low; }
// 递归 int binary_search(vector<int>& nums, int target, int low, int high) { if (low > high) return low; int mid = low + (high - low) / 2; if (nums[mid] > target) { return binary_search(nums, target, low, mid - 1); else if (nums[mid] < target) { return binary_search(nums, targetm mid + 1, high); else { return mid; } }
数组中有重复的元素
寻找元素第一次出现的位置。相当于C++中的lower_bound()函数（寻找第一个大于等于目标值的元素位置）。代码如下
int firstOccurrence(vector<int>& nums, int target) { int low = 0, high = nums.size() - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] < target) low = mid + 1; else high = mid - 1; } return low; }
int firstOccurrence(vector<int>& nums, int target, int low, int high) { if (low > high) return low; int mid = low + (high - low) / 2; if (nums[mid] < target) return firstOccurrence(nums, target, mid + 1, high); else return firstOccurrence(nums, target, low, mid - 1); }
（1）找出一个有序数组nums中是否含有target值。如果存在返回target值的索引，如果不存在返回-1。这个算法仅考虑了target的存在性，不考虑target的位置和个数。
int binary_search(vector<int>& nums, int target, int left, int right) { while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; else return mid; } return -1;
}
（2）找出一个有序数组中是否含有target值，如果存在返回target第一次出现的索引，如果不存在返回-1。
(题目来源于LintCode，具体解法详见[LintCode] First Position Of Target)
class Solution { public: /** * @param nums: The integer array. * @param target: Target number to find. * @return: The first position of target. Position starts from 0. */ int binarySearch(vector<int> &array, int target) { // write your code here if (array.empty()) return -1; int left = 0, right = array.size() - 1; int mid = 0; while (left <= right) { mid = left + (right - left) / 2; if (array[mid] < target) left = mid + 1; else right = mid - 1; } if (array[left] == target) return left; else return -1; } }; // 1335 ms
（3）给定一个有序数组找出给定目标值 target 的起始和结束位置。如果目标值不在数组中，则返回[-1, -1]
利用上题中的寻找target左边界的思路，很容易通过修改if判断来找出target右边界。
(题目来源于LintCode，具体解法详见[LintCode] Search For A Range)
class Solution { public: /* * @param A: an integer sorted array * @param target: an integer to be inserted * @return: a list of length 2, [index1, index2] */ vector<int> searchRange(vector<int> &A, int target) { // write your code here if (A.empty()) return {-1, -1}; int lower = 0, upper = 0, mid = 0; int left = 0, right = A.size() - 1; while (left <= right) { mid = left + (right - left) / 2; if (A[mid] < target) left = mid + 1; else right = mid - 1; } lower = left; left = 0, right = A.size() - 1; while (left <= right) { mid = left + (right - left) / 2; if (A[mid] > target) right = mid - 1; else left = mid + 1; } upper = right; if (lower <= upper) return {lower, upper}; else return {-1, -1}; } }; // 816 ms
Tips：
// 二分值越大越符合条件，要求符合条件的最小值 while (l < r) { mid = (l + r) / 2; if (不符合条件) l = mid + 1; else r = mid; }
// 二分值越小越符合条件，要求符合条件的最大值 while (l < r) { mid = (l + r + 1) / 2; if (符合条件) l = mid; else r = mid - 1; }