使用二分查找的前提条件：

• 有序（单调递增或递减）

• 存在边界

• 能够通过索引访问

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在数据规模的对数时间复杂度内完成查找。但是，二分查找要求线性表具有有随机访问的特点（例如数组），也要求线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。

代码模板：

public int sort(int[] nums, int target){
    int left = 0;
    int right = nums.length-1;
    while(left < right){
        int mid = (left+right)/2;
        if(nums[mid] == target ){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
}

例题1：

LeetCode ——69.x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4 输出: 2 示例 2:

输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

class Solution {
    public int mySqrt(int x) {
        
        if (x==0 || x==1) return x;
        
        int left = 0;
        int right = x/2+1;
        int res = 0;
        while(left <= right){
            int mid = (left + right)/2;
            if(mid == x/mid){
                return mid;
            }else if(mid < x/mid){  //取小，防止过大
                left = mid +1;
                res = mid;
            }else{
                right = mid -1;
            }
        }
        return res;
    }
}

例题2：

剑指offer 53 - II 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3] 输出: 2 示例 2:

输入: [0,1,2,3,4,5,6,7,9] 输出: 8

解法一：个人套模板解法

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0]==0 ?1:0;
        if(nums[len-1]== len-1) return len;
        if(nums[0]!=0) return 0;

        int left = 0;
        int right = len -1;
        int mid = 0;
        while(left <= right){
            mid = (left + right)/2;
            if(nums[mid]>mid && nums[mid-1]==mid-1){
                return mid;
            }else if(nums[mid] == mid ){
                left = mid + 1;
            }else if(nums[mid]>mid){
                right = mid - 1;
            }
        }
        return mid;
    }
}

执行结果：（内存消耗更少）

解法2：网上大佬的解法（代码更简洁）

class Solution {
    public int missingNumber(int[] nums) {

        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        while(left <= right){
            mid = (left + right)/2;
            if(nums[mid] == mid)  left = mid +1;
            else right = mid -1;
        }
        return left;
    }
}

执行结果：

以上是我个人学习总结的笔记，当然目前还是还是不够的，对于二分法的理解还要多刷题，多思考，多理解！