1 经典二分搜索（Classical Binary Search）

1 题目

??经典二分搜索（Classical Binary Search）

lintcode：题号——457，难度——easy

2 描述

??在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回 -1。

样例 1：

输入：nums = [1,2,2,4,5,5], target = 2
输出：1 或者 2

样例 2：

输入：nums = [1,2,2,4,5,5], target = 6
输出：-1

3 思路

??对有序数组可以直接使用二分法，即拿着目标元素与中间位置的元素进行比较，判断目标元素在当前位置的左区间还是右区间，再在目标区间内再次执行二分法，直到把子区间缩小到只有一个元素，即可找到或者不存在。

1. 找到中间位置的元素；
2. 与目标元素比较，确定目标元素所在的区间，缩小目标区间；
3. 重复以上操作，直到找到或者结束。

3.1 图解

3.2 时间复杂度

??算法的时间复杂度为O(log n)。

3.3 空间复杂度

??算法的空间复杂度为O(1)。

4 模版

??算法虽然简单，但是在边界的处理上如果不注意的话很容易就产生“死循环”、“漏元素”、“越界”的情况，产生的原因有很多，例如：

1. 计算机的数据运算都是偏左的（给整数赋值“4.9”会被自动转成“4”，不是四舍五入）
2. 比较大小的时候取“>”、“<”、">="、">="，会产生不同效果
3. 缩小区间时候取不取当前的中间元素，有可能导致死循环
4. 在数组的头部和尾部要考虑越界的情况

??为解决上述问题，分享一个通用的二分法算法的模版，需要注意的点有四个，分别如下：

1. mid = start + (end - start) / 2
2. start + 1 < end
3. A[mid] ==, <, >
4. A[start] A[end] ? target

1. 取中点的时候使用start + (end - start) / 2，不使用(start + end) / 2，防止start和end很大的时候，start + end在整型范围内越界；
2. 循环退出条件使用start + 1 < end，不使用start < end，防止死循环；
3. 循环内的判断使用==、<和>单独处理各个分支，不使用组合符号<=和>=，防止死循环；
4. 因为第二点的原因，所以循环退出后需要单独判断一次当前的start和end位置的元素。

5 源码

??注意事项：

1. 最后是与target比较，不要写错成与start、end比较；
2. return的是index还是value要看清楚。

??C++版本：

/**经典二分搜索算法
* @param nums 有序数组
* @param target 目标元素的值
* @return 目标元素在有序数组中的位置（下标序号）
*/
int findPosition(vector<int> &nums, int target) {// write your code hereif (nums.empty()){return -1;}int start = 0;int end = nums.size() - 1;int mid = 0;while (start + 1 < end) // 第二点：循环条件{mid = start + (end - start) / 2; // 第一点：取中点元素if (nums.at(mid) == target) // 第三点：单独处理各个分支{return mid;}if (nums.at(mid) < target){start = mid;}if (nums.at(mid) > target){end = mid;}}if (nums.at(start) == target) // 第四点：处理循环退出后的start和end{return start;}if (nums.at(end) == target){return end;}return -1;
}