二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，但查找的序列必须是有序的。每次查找的时候都是用目标值和查找区间内的中间值比较，查找的步骤如下：
- 如果目标值等于中间值，说明找到了，直接返回。
- 如果目标值大于中间值，说明中间值以及前面部分太小了，下一步需要往后半部分查找。
- 如果目标值小于中间值，说明中间值以及后面部分太大了，下一步需要往前半部分查找。
这样每次查找之后都可以砍掉一半，所以它的时间复杂度是log_2n 。比如要在下面有序数组中查找数字 9 ，查找步骤如下图所示。
这里使用的是左闭右闭 [left,right]区间，循环的终止条件是区间为空，没有数据可查询了，只要 left <= right ，就可以继续查找，当 left == right 的时候，说明区间只有一个数字，还可以继续查询。当 left > right 的时候，说明可查询区间为空了。所以可查询的条件就是 left <= right ，循环终止的条件是 left > right，来看下代码：
public int search(int[] nums, int target) {
int left = 0;// 查找的左边界。
int right = nums.length - 1;// 查找的右边界
while (left <= right) {// 有效区间内继续查找。
// 找到区间内的中间元素。
int mid = (left + right) >>> 1;// 这里不用担心是否溢出。
if (target == nums[mid])// 如果找到直接返回。
return mid;
else if (target < nums[mid])// 如果查找的值小于中间元素，缩小右边界。
right = mid - 1;
else
left = mid + 1;// 如果查找的值大于中间元素，缩小左边界。
}
return -1;// 没找到，返回 -1 。
}
还可以改成递归的写法。
public int search(int[] nums, int target) {
return helper(nums, target, 0, nums.length - 1);
}
private int helper(int[] nums, int target, int left, int right) {
if (left > right)// 可查找区间为空，返回 -1 。
return -1;
int mid = (left + right) >>> 1;
if (target == nums[mid])
return mid;// 找到直接返回。
else if (target < nums[mid])
return helper(nums, target, left, mid - 1);// 在左边部分查找。
else return helper(nums, target, mid + 1, right);// 在右边部分查找。
}
上面查找的范围是左闭右闭区间，也就是 [left，right] ，循环的终止条件是 left>right ，我们来改成左闭右开区间，也就是 [left，right) ，因为区间不包含 right ，所以可以查询的条件是 left < right ，如果 left >= right 说明查找的区间为空，直接退出就行了，这里只需要改变 3 个地方即可，看下代码。
// 左闭右开[left，right)。
public int search(int[] nums, int target) {
int left = 0;// 查找的左边界，闭区间。
int right = nums.length;// 查找的右边界（1，改变），开区间。
while (left < right) {//（2，改变）。
int mid = (left + right) >>> 1;
if (nums[mid] == target) {// 如果找到了就直接返回。
return mid;
} else if (nums[mid] < target) {
left = mid + 1;// 下一步往后半部分找。
} else {// if (nums[mid] > target)
// 下一步往前半部分找，因为right是开区间，把mid赋值给right，相当于把mid也排除掉了。
right = mid;//（3，改变），
}
}
// 如果没找到就返回-1
return -1;
}
二分查找的区间常见的有左闭右闭和左闭右开两种，无论使用哪种都是可以的，只需要分清哪些是无效的空间把它砍掉即可，还要防止在 while 中出现死循环的情况。
插入位置
给定一个没有重复数字的排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它按顺序插入的位置。
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
如果找到就返回，如果没找到就返回目标值应该插入的位置。最简单的就是使用左闭右开区间，因为右区间是开区间，不在查找范围内，但有可能是需要插入的位置。解题步骤如下：
- 使用两个指针一个指向查询区域的左端 left ，一个指向查询区域右端的下一个位置 right ，每次取区域内 [left，right) 中间位置的值。
- 如果目标值等于中间值，说明找到了，直接返回 mid 。
- 如果目标值大于中间值，说明中间值及前面部分太小了，下一步需要往后半部分查找 [mid+1,right) 。
- 如果目标值小于中间值，说明中间值及后面部分太大了，但中间值有可能是需要插入的位置，所以中间值的位置不能排除，下一步需要往前半部分查找 [left,mid) 。
因为 right 是开区间，当 left >= right 的时候说明查询区间为空，终止循环，所以循环执行的条件是 left < right 。
来看下代码：
// 左闭右开
public int searchInsert(int[] nums, int target) {
int left = 0;// 左边界，闭区间。
int right = nums.length;// 右边界，开区间。
while (left < right) {
int mid = (left + right) >>> 1;// 中间值。
if (nums[mid] == target)
return mid;
else if (nums[mid] < target) {
left = mid + 1; // 缩小范围到[mid+1,right]
} else {// if (nums[mid] > target)
right = mid; // 缩小范围到[left,mid)
}
}
return right;// 或者return left;
}
这题能不能使用左闭右闭区间呢？实际上也可以，不过这里要注意出现死循环的情况，先来看下代码。
// 左闭右闭
public int searchInsert(int[] nums, int target) {
int left = 0;// 左边界，闭区间。
int right = nums.length - 1;// 右边界，闭区间。
while (left <= right) {
int mid = (left + right) >>> 1;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target) {
left = mid + 1; // 缩小范围到[mid+1,right]
} else {// if (nums[mid] > target)
if (left == right)// 防止死循环。
return right;
// 缩小范围到[left,mid]。
right = mid;
}
}
return left;// 不能返回right。
}
二分法查找的时候要记住一点：无论是开区间还是闭区间，每次 while 循环的时候，两个指针必须要有一个指针的值发生改变。这一点是非常重要的，如果两个指针的值都不发生改变，那么 mid 值就不会改变，下一轮循环两个指针的值还是不会变，所以就会出现死循环。解决死循环这个问题很简单，只要保证两个指针每次循环之后有一个改变就行了。
- 如果两个指针的值相差大于 1 是不会出现死循环的，因为大于 1 的时候 mid 值和任何一个指针的值都不相等，如果有特殊的情况也要注意，比如 left=mid-1，或者right=mid+1等非正常的赋值。
- 如果两个指针的值相差等于 1 ，mid 值就会等于 left ，在计算的时候要避免 mid = left 的情况，如果非要这样做，需要做一些特殊的判断。或者计算 mid 值的时候，让他等于中间的后一个，也就是 mid = (left + right +1) >>>1 ，如果这样计算还要避免出现 mid = right 以及数组越界的情况。
- 如果两个指针的值相等，就会出现 left ，right 和 mid 都相等，这个时候也要避免 right 赋值给任何一个指针。
我们来看几个出现死循环的示例，最后一种不会出现死循环，前面 4 个都会出现。
// 可能出现死循环
public int searchInsert1(int[] nums, int target) {
int left = 0;
int right = 右区间;
while (left < right) {
int mid = (left + right) >>> 1;
// ……
// 当 left+1==right 的时候，mid 就会等于 left ,如果像下面这样赋值
// 相当于 left 和 right 值都没有改变，出现死循环。
left = mid;
}
return left;
}
// 可能出现死循环
public int searchInsert2(int[] nums, int target) {
int left = 0;
int right = 右区间;
while (left < right) {
int mid = (left + right) >>> 1;
// ……
// 当 left+1==right 的时候，mid 就会等于 left ， mid + 1 就等于 right 。
// 如果像下面这样赋值相当于 left 和 right 值都没有改变，出现死循环。
right = mid + 1;（一般是right=mid，或者right=mid-1。这种赋值出现的少，但也要注意）
}
return left;
}
// 可能出现死循环
public int searchInsert3(int[] nums, int target) {
int left = 0;
int right = 右区间;
while (left < right) {
// 这样计算还要注意越界的问题，如果 right 最开始的时候
// 赋值为 nums.length-1 不需要考虑越界问题。
int mid = (left + right + 1) >>> 1;
// ……
// 当 left+1==right 的时候，mid 就会等于 right ,如果像下面这样赋值
// 相当于 left 和 right 值都没有改变，出现死循环。
right = mid;
}
return left;
}
// 可能出现死循环
public int searchInsert4(int[] nums, int target) {
int left = 0;
int right = 右区间;
while (left <= right) {
int mid = (left + right) >>> 1;
// ……
// 当 left==right的时候，left，right 和 mid 都相等，不能
// 出现 left = mid 或 right = mid 这种情况，否则会出现死循环。
// 当 left +1 = right 的时候，也要注意。
left = mid;
// 或者
right = mid;
}
return left;
}
// 不会出现死循环
public int searchInsert5(int[] nums, int target) {
int left = 0;
int right = 右区间;
while (left < right) {
int mid = (left + right) >>> 1;
// 因为循环结束的条件是 left==right ，所以循环中left不可能等于right，
// 计算mid值的时候是往下取值，所以mid不可能等于right，不会出现死循环。
right = mid;// 不会出现死循环。
// 如果这样赋值left = mid;会出现死循环，因为mid往下取值可能等于left。
}
return left;
}
上面几种情况都有可能出现死循环，可以看到出现死循环的情况要么是 left = mid ，要么是 right = mid ，所以当出现这两种情况的话要特别注意。至于区间的起始位置和结束位置以及最后的返回值可以根据不同的要求做不同的调整。如果确实需要上面那几种写法也是可以的，只需要在代码中做进一步的判断即可。在 while 循环中，如果循环的终止条件是 left < right ，那么循环结束之后 left == right ，最后返回 left 和 right 都一样，如果循环的终止条件是 left <= right ，循环结束之后 right + 1 = left ，究竟返回哪个需要根据不同的题做不同的调整。我们再来看上面这题的另一种写法。
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target) {
// 缩小范围到[mid+1,right]
left = mid + 1;
} else {// if (nums[mid] > target)
// 缩小范围到[left,mid-1]
right = mid - 1;//
}
}
// 因为循环的终止条件是left>right，所以这里不能返回right，只能返回left。
return left;
}
这种解决方式可能是大家最困惑的，不是说 mid 也有可能是插入位置吗，怎么把它也删掉了，实际上这也不影响结果。因为假设 mid 值是要插入的位置，那么 left 和 right 相等的时候必定是在 mid 的前一个位置 (除了 mid 等于0的时候)，而循环终止的条件是 left > right ，所以 left 就是我们要插入的位置。
第一个和最后一个位置
给定一个升序数组 nums，和一个目标值 target，找出给定目标值在数组中的开始位置和结束位置，如果没找到返回 -1 。
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
这题让找出目标值在数组中开始和结束的位置，我们先来看下这题的大致代码：
public int[] searchRange(int[] nums, int target) {
// 现在开始的位置，如果开始的位置没有，那么结束的位置也没有。
int first = findFirst(nums, target);
if (first >= nums.length || nums[first] != target)
return new int[]{-1, -1};
// 如果开始的位置有，再查结束的位置。
return new int[]{first, findLast(nums, target)};
}
先查找开始的位置，如果找到，再查结束的位置。我们先来看下查找开始位置的函数。这题不同的写法非常多，先来看下左闭右闭区间的解法。
- 如果中间值 mid 指向的值等于目标值，要缩小右边界，让 right 的值等于 mid 。因为 mid 等于要查找的值，不能排除。能不能让 left 的值等于 mid 呢？实际上是不行的，因为这样的话 left 前面如果还有等于目标值的，会被排除掉。
- 如果中间值 mid 指向的值小于目标值，缩小左边界，让 left 等于 mid + 1 。
- 如果中间值 mid 指向的值大于目标值，缩右左边界，让 right 等于 mid – 1 。
这里要注意第一种情况会可能出现死循环，所以要判断下，代码如下：
// 查找第一次出现的位置，左闭右闭区间。
int findFirst(int[] nums, int target) {
int left = 0;// 左边界，闭区间
int right = nums.length - 1;// 右边界，闭区间。
while (left <= right) {
int mid = (left + right) >>> 1;
if (nums[mid] == target) {
// 当left==right的时候，也就是区间只有一个元素的时候，mid才有可能等于right。
if (mid == right)
return left;
right = mid;
} else if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
或者像下面这样，当只有一个区间的时候不需要判断，直接返回，这样就不会出现死循环的情况了。
int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] == target)
right = mid;
else if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
我们再来看另一种解法，如下所示，这种情况当 left == right 或者 left +1 == right 的时候，mid 值等于 right ，有可能出现死循环，所以要特殊判断下。
int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right + 1) >>> 1;// 修改地方。
if (nums[mid] == target) {
if (mid == right)
return nums[left] == target ? left : right;
right = mid;// 这里容易出现死循环，所以上面要判断下。
} else if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
或者我们也可以把它合并下，代码如下，这里大家可能好奇为什么当 target == nums[mid] 的时候，要让 right = mid – 1 ，把 mid 给排除掉了。这是因为循环终止的时候 left = right +1 ，也就是说如果 mid 指向的是开始的位置，那么他前面都是小于开始的位置，让 mid 等于 right ，直到循环结束 right 都不会在变了，而循环结束的时候是 left = right +1 ，也就是 left 指向的是开始的位置，最后只需要返回 left 即可。
int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (target > nums[mid])
left = mid + 1;
else
right = mid - 1;
}
return left;
}
当 target == nums[mid] 的时候，我们也可以不把 mid 给排除掉，如下所示，因为 while循环终止的条件是 left == right ，所以不会出现死循环。
int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right) >>> 1;
if (target > nums[mid])
left = mid + 1;
else
right = mid;
}
return left;
}
上面使用的是左闭右闭区间，我们再来看下左闭右开区间怎么计算。先看第一种，也是最简单的，这种情况不会出现死循环，直接写就好了。
int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] == target)
right = mid;
else if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
上面写法中当 left +1 == right 的时候，取的中间值是 left ，我们还可以取 right 作为中间值，取 right 作为中间值的时候需要判断死循环以及越界问题，代码如下。
int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right + 1) >>> 1;
// 这种情况不但要处理死循环问题还要处理越界问题。
if (mid == nums.length || nums[mid] == target) {
if (mid == right)
return nums[left] == target ? left : right;
right = mid;
} else if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
也可以合并下，代码如下，当 right 指向目标值的时候，他会一步步往前挪，当挪到开始值的时候会停下了。
int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (target > nums[mid])
left = mid + 1;
else
right = mid;
}
return left;
}
我们看到就一个查询开始的位置就有那么多种写法，二分法做的就是每次循环都会砍掉一半的无效数据，只需要搞懂哪些是需要砍掉的，哪些是需要保留的，还有在双指针赋值的时候保证一定要改变原来的值，掌握这些，二分法查找基本上就很容易写了。
再来看下查找结束的位置，和查找开始的位置类似，这个就不在细讲。
来看下代码：
int findLast(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (target == nums[mid]) {
if (mid == left)
return nums[right] == target ? right : left;// 这里先判断右边。
left = mid;// 注意这里会出现死循环。
} else if (target > nums[mid])
left = mid + 1;
else
right = mid - 1;
}
return left;
}
这个是左闭右闭区间，我们再来看下左闭右开区间，代码如下。
int findLast(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (target == nums[mid]) {
if (left == mid)
return left;
left = mid;// 注意这里会出现死循环。
} else if (target > nums[mid])
left = mid + 1;
else
right = mid;// 开区间，这里不能写right=mid+1。
}
return left;
}
这题写法非常多，有兴趣的大家也可以参照查找开始的位置继续写，这里就不在往下写了。
