二分查找模板

二分查找主要难点在于边界判定，逻辑相对简单，下文以力扣704.二分查找为例分析二分查找的代码模板。

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 来源：力扣（LeetCode） 原题地址

问题分析

在有序数组中找到一个数，一般的思路是将整个数组遍历一遍，最坏的情况下时间复杂度为O(n)，在一些数据量特别大的情况下会超时。此时我们可以用二分法进行查找————由于是有序数组，将数组中间的元素与需要找到的元素进行比较，便可判断需要查找的元素在数组的前半部分或者后半部分。接下来进行同样的操作，进一步缩小范围。这样下来时间复杂度为O(logn)，大大减少。

实现思路

虽然二分法的思路简单，但实现起来并不容易。它的问题主要在边界判断上。接下是具体实现思路：

1. 首先定义数组的左端点与右端点：left, right。

2. 当left < right，也就是我们所确定的数组所包含的元素个数大于1时：

3. 确定一个middle = (left + right) / 2（如果是python的话要用//）。

4. 如果需要查找的target比middle大，说明target就在数组右半边，这时候我们可以更新左端点，使left = middle + 1，从而开始新一轮对右半边数组的查找。反之我们就要更新右端点，使right = middle。

   以下是具体实现代码：

   size = nums.size();
   int left = 0, right = size;
   bool flag = true;
   while (left < right)
   {
       int mid = (left + right) / 2;
       if (target > nums[mid]) left = mid + 1;
       else if (target < nums[mid]) right = mid;
       else cout << mid, flag = false;
   }
   if (flag) cout << -1;

   注意，这里我们使用的是左闭右开区间。middle已经判断过，不在target所在区间。因为右开，右端点right不会访问到，所以我们可以令right = middle。但由于左闭，左端点是可以被访问到的，所以我们要让left = middle + 1，在middle的基础上向左移动一位。

代码实现

二分查找 - AC代码