二分查找的思想：通过不断缩小搜索区间的范围，直到找到目标元素或者没有找到目标元素，这里的不断缩小搜索区间是一种减而治之的思想，也称为减治思想。

1.减而治之

思想简介

减就是减少规模的意思，治就是解决的意思。减治思想从另一个角度来说，是排除法，意思就是每一轮排除掉一定不存在元素的区间，在剩下可能存在目标元素的区间里面继续查找。每一次通过一些判断和操作，使问题的规模逐渐减少。

?举个栗子

猜价格游戏：给出一个商品，告诉答题者它的价格在多少元（价格为整数）以内，让答题者猜，如果猜出的价格低于真正价格，就说少了，高于真正的价格，就说多了，看谁能在最短的时间内猜中。这个游戏就是应用减治思想完成猜价格任务的。多了或少了，就是给参与游戏的人反馈，让游戏者逐渐缩小价格区间，最终猜中价格。

2.应用范围

在有序数组中进行查找一个数(二分下标)

注意两个重要条件有序和数组。数组具有随机访问的特性，他在内存中连续存放，因此我们可以通过数组的下标快速访问到这个元素。如果存放在链表中，需要访问某一个元素还需要一个一个遍历，所以链表不适合使用二分查找。

在整数范围内查找一个整数(二分答案)

如果我们要找一个整数，并且我们知道这个整数的范围，那么就可以使用二分查找算法，逐渐缩小整数的范围。

?举个栗子：

如果我们要找的数最小值为0，最大值为X，那么我们可以把他想象为一个数组[0,1,2,...,X]里的一个值，这个数组的下标和值是一样的，找到数组的下标就等于找到数组的值。

这种二分法用于查找一个有范围的数，也被称为二分答案，或者二分结果，也就是在结果区间里逐渐缩小目标元素的范围。

3.两种思路

1) 在循环体中查找元素

① 最基本的问题

参考力扣704题。题目要求我们在一个有序数组里查找目标元素的下标，目标元素不存在，返回-1。

分析：由于数组的有序且升序的数组，二分查找的思路是，先看位于数组中间的那个元素的值。

• 如果中间的那个元素正好等于目标元素，我们就可以直接返回这个元素的下标；
• 否则我们就需要在中间这个元素的左边或者右边继续查找。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        //目标数target存在于区间[left,right]
        while(left<=right){
            //定义中间数
            int mid = (left+right)/2;
            if(nums[mid]==target) return mid;
            //中间数小于目标数那么缩小区间到[mid+1,right]
            if(nums[mid]<target) left = mid+1;
            //中间数大于目标数那么缩小区间到[left,mid-1]
            else right = mid;
        }
        //找不到目标数
        return -1;
    }
}

说明：

• 这里用的是二分查找算法的思路1，在循环体中找到了元素就直接返回；
• 每一次都在一个区间里搜索目标元素，表示这个区间的两个变量就是这个区间的左右边界，我们分别用left和right，最开始的时候left为0，right为数组长度-1；
• 接下来我们在循环体中处理，循环的条件为left<=right，表示在区间里还有元素的时候，执行内部的逻辑；
• 退出循环后，说明数组不存在目标元素，根据题意返回-1；

复杂度分析：

• 时间复杂度：二分查找的时间复杂度为O(logN),这里的N是数组的长度；
• 空间复杂度：只用到了常数个临时变量，空间复杂度为O(1)；

② 细节(重点)

(1)循环可继续条件：

while(left<=right)表示在区间内，还剩下一个元素的时候，我们还要继续查找，因为这种循环的查询返回条件是在内部进行的意思就是说 当我在循环体内部找到我要的值过后，我就直接返回了，不会再继续进行循环操作了。

(2)取中间数的代码：

取中间数的代码

int mid = (left+right)/2;

注意一个问题int类型的最大值为2147483647，left+right这个操作可能会发生整型溢出这个时候推荐写法为:

>int mid = left+(right-left)/2;

这时候要说明的是 /2 表示为下取整。所谓下取整，就是取中间位置元素的时候，取的是中间靠左的这个位置，那么可以取中间靠右这个位置的值吗？答案是可以的，我们把取中间值的代码改造一下

int mid = left+(right-left+1)/2;

通过测试发现，这样取中间值还是可以通过的。那么这是为什么呢？原因其实很简单，因为我们的思路是根据中间值去决定下一轮搜索哪个区间，每一轮需要考虑的那个元素不一定非得是中间那个元素，靠左靠右都是可以的。一般而言，取位于区间起点二分之一处，这样写简单，而且在平均意义下效果最好。

有些写法会把/2写为>>1;这种是因为右移1位就等同于除以了2，这样写的原因是因为位运算比整除运算要快一点。事实上，高级的编程语言，对于/2和除以2的方幂的时候，在底层都会将其转为位运算。还有一种写法:

int mid = (left+right)>>>1;

解释一下>>1和>>>1的区别>>1的意思是带符号右移一位，而>>>1的意思是无符号右移一位,1是代表移动的位数，当(left+right)发生整型溢出的时候，右移一位由于高位补零，结果依然正确。虽然整型溢出的概率非常低，但是我们还是得避免他，所以推荐的写法为:

int mid = left + ((right-left)>>1);

③针对 力扣704题 ，还有一种递归解法

class Solution {
   public int search(int[] nums, int target) { 
        return search(nums, 0, nums.length - 1, target);
    }
    public int search(int[]nums,int left,int right,int target){
        //递归终止条件
        if(left>right) return -1;
        //确定中间值
        int mid = left+((right-left)>>1);

        if(nums[mid]==target) return mid;
        //中间数小于目标数那么缩小区间到[mid+1,right]
        if(nums[mid]<target) return search(nums,mid+1,right,target);
        //中间数大于目标数那么缩小区间到[left,mid-1]
        else return search(nums,left,mid-1,target);
    }
}

2) 在循环体中排除目标元素一定不存在的区间

①通过排除法解决二分问题

还是用 力扣704题 的例子，这次换一个写法

class Solution {
   public int search(int[] nums, int target) {
       int left = 0;
       int right = nums.length-1;
       while(left<right){
           int mid = left+((right-left)>>1);
           if(nums[mid]<target){
               left = mid+1;
           }else{
               right = mid;
           }
       }
       return nums[left] == target? left : -1;
   }
}

class Solution {
   public int search(int[] nums, int target) {
       int left = 0;
       int right = nums.length-1;
       while(left<right){
           int mid = left+((right-left+1)>>1);
           if(nums[mid]<=target){
               left = mid;
           }else{
               right = mid-1;
           }
       }
       return nums[left] == target? left : -1;
   }
}

之前讲的是当left==right，左右边界重合，区间还有1个元素的时候，二分查找的逻辑还需要继续执行,因为他的返回条件是在循环体内部的，如果退出了循环体那么表示没有查找到我们需要查找的元素。

可以很直观的发现，现在循环可继续的条件变成了while(left<right)，这说明当left==right的时候，就退出了循环，这表示区间里面只剩一个元素的时候，这个元素可能就是我们要找的元素。所以在退出循环后，需要再做一次判断。这样写的话只是把区间分成了两个部分，所以在写代码的时候需要考虑的因素就会更少，而且在思考缩小待搜索区间的逻辑时，只需要考虑其中一种情况，另一种情况得到的区间就正好是上一个区间的反面区间。

缩小问题区间的通常思路就是：先思考要找的数的性质，然后对这个性质取反，也就是：先讨论看到的中间位置的元素在什么情况下不是目标元素。

例题中我们要找的是==target元素，对这个性质取反，就是!=target,也就是<target或>target

②需要用到上取整的原因

①中的两段代码，第一段是下取整，第二段是上取整，现在解释一下为什么要上取值。

二分会把区间分为两个区间一个是可能存在目标元素的区间，一个是一定不存在目标元素的区间。

如果mid被分到左边区间

这个时候区间被分为两个部分：[left,mid]和[mid+1right]，对应边界限制代码为left=mid+1和right=mid

如果mid被分到右边区间

这个时候区间被分为两个部分：[left,mid-1]和[mid,right]，对应边界限制代码为left=mid和right=mid-1

值得注意的是，在mid被分到右区间时，一定要将取中间数改为上取整，也就是括号里+1。这是因为[left,right]区间里只剩下两个元素的时候，如果mid是下取整，一旦进入left=mid，那么区间将不会缩小，下一轮搜索区间还是[left,right],会一直循环下去导致死循环。

解决方法也很简单，在最后一次循环的时候，在取中间数时改为上取整，但是这个循环是一个while循环，不好做最后一次循环的判断，所以直接让整个循环都上取整就能解决问题了。

③要点总结

• 循环终止条件写为left<right,表示退出循环的时候只剩下一个元素;
• 在循环体内考虑如何缩减待搜索区间，也可以认为是在待搜索区间里排除一定不存在目标元素的区间;
• 根据中间数被分到左边和右边区间，来调整取中间数的行为；
• 缩小待搜索区间有效的办法是：从nums[mid]满足什么条件的时候一定不是目标元素去考虑，进而考虑mid的左边元素和右边元素哪一边可能存在目标元素;
• 当left=mid时，取中间数需要上取整，可以避免死循环;
• 退出循环时，需要单独判断剩下的那个元素是不是目标元素;

④写法要点

right = mid 和 left = mid+1 和 int mid = left+((right-left)>>1); 一定是配对出现的;

right = mid-1 和 left = mid 和 int mid = left+((right-left+1)>>1); 一定是配对出现的;