3.二分搜索

定义

Step1：计算数据的中点索引值m = (i+j)/2 向下取整 。i为首元素索引，j为尾元素索引。
Step2：判断 nums[m] 和target 的大小关系，分为以下三种情况。

1. 当 nums[m] < target 时，说明 target 在区间中：
   i = m + 1
2. 当 nums[m] > target 时，说明 target 在区间中:
   j = m -1
3. 当 nums[m] = target 时，说明找到 target ，返回索引m 。

具体应用场景

1）在有序数组中确定num存在还是不存在

//查找是需保证nums[]为有序的
    public static int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {  //如果是空则返回-1
            return -1;
        }
        int i = 0,j = nums.length-1,m = -1; //i为数组首元素索引，j为数组尾元素索引,m为中点索引
            while (i<=j){
                m = (i + j)/2;
                if (nums[m] == target){
                    return m;
                } else if (nums[m] > target) {//2. 当nums[m] > target时，说明target在区间中：j = m -1
                     j = m-1;
                }else {//1. 当nums[m] < target时，说明target在区间中：i = m + 1
                    i = m+1;
                }
            }
        return -1;//没有找到target，返回-1
    }

2）在有序数组中找≥=target的最左位置

  //在有序数组中找>=target的最左位置，需要nums[]有序
    public static int findLeft(int nums[],int target){
        int ans = -1;//返回值，初始化为-1，找到符合要求的值n后改为n的索引值，没有找到就为-1
        int i = 0, j = nums.length-1,m = 0;
        while (i<=j){
            m = (i + j)/2;
            if (nums[m] >= target){//如果nums[i]>=target
                ans = m;//更新ans的值为nums[i]的索引ji
                j = m-1;//调整右边界索引
            }else {
                i = m+1;//如果nums[i]<target，则nums[i]左侧位置都比target小，所以调整二分等我左边界
            }
        }
        return ans;
    }
}

3）在有序数组中找<=target的最右位置

   //查找在有序数组中找<=target的最右位置
    public static int findRight(int nums[], int target) {
        int ans = -1;//返回值，初始化，为-1，找到符合要求的值n后改为n的索引值，没有找到就为-1
        int i = 0, j = nums.length - 1, m = 0;//i为左边界索引，j为右边界索引，m为重点索引
        while (i <= j) {
            m = (i + j) / 2;
            if (nums[m] <= target) { //如果nums[m]<=target,证明nums[m]左侧位置都小于target
                ans = m;//更新ans的值
                i = m + 1;//更新左边界
            } else {//如果nums[m]>m.证明小于target的值在m位置的左侧
                j = m - 1;//更新右边界
            }
        }
        return ans;
    }

4）二分搜索不一定发生在有序数组上（比如寻找峰值问题）

//查找峰值问题，nums[]不要求有序
    /**
     * 峰值元素是指其值严格大于左右相邻值的元素
     * 给你一个整数数组 nums，已知任何两个相邻的值都不相等
     * 找到峰值元素并返回其索引
     * 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
     * 假设 nums[-1] = nums[n] = 无穷小
     */
    public static int findPeakElement(int nums[]) {
        if (nums.length == 0) {//如果是空数组则返回1；
            return -1;
        }
        if (nums.length == 1) {//如果数组长度为1.怎nums[0]就是峰值点
            return 0;
        }
        if (nums[0] > nums[1]) {
            return 0;
        }
        if (nums[nums.length - 1] > nums[nums.length - 2]) {
            return nums.length - 1;
        }
        int l = 1, r = nums.length - 2, ans = -1;//上面if语句判断过0和n-位置是否为峰值点，所以如果不是就更新左右边界为1和n-2
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] < nums[m - 1]) {//数组最左边界为上升，若m位置小于m-1位置，则m~m-1位置为开口向下的二次函数，则在这段区间存在峰值。
                r = m - 1;//更新右边界为中点左侧
            } else if (nums[m] < nums[m + 1]) {//数组最右边界为下降，若m位置小于m+1位置，则m~m+1位置为开口向下的二次函数，则在这段区间存在峰值。
                l = m + 1;//更新左边界为中点右侧
            } else {//如果m位置大于m-1和m+1位置，则m位置为峰值
                ans = m;
                break;
            }
        }
        return ans;
    }

5）“二分答案法”这个非常重要的算法,左神后续讲解

测试链接 : https://leetcode.cn/problems/find-peak-element/