二分搜索 （左程云）

$$二分搜索$$

在$有序$的数组中确定num是否存在

二分法应用的最常见也是最简单的场景，就是确定一个有序的数组中是否存在某个元素$num$。
经典二分代码：

public static boolean exist(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return false;
    }
    int l = 0, r = arr.length - 1, m = 0;
    while (l <= r) {
        m = l + (r - l) / 2;
        if (arr[m] == num) {
            return true;
        } else if (arr[m] > num) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return false;
}

❗$m=l+(r-l)/2;$：可以防止$int$数据的溢出，也可以写成$m=l+(r-l)>>1$，位运算操作。

⭐⭐⭐在有序的数组中寻找 >= num 的最左的位置

也就是说找的是 >= $num$最小的元素位置。
关键在于二分的方向：
① 如果$mid$处的元素 >= $num$，那么$mid$处元素是不是最左侧的 >= $m$的元素呢？并不知道，可能$mid$的左边还有元素满足条件，于是这种情况应该向左二分（区间左缩）。并且应该记录当前的$mid$下标，万一$mid$左边没有符合条件的元素了，那么$mid$下标就是答案。
② 如果$mid$处元素 < num，显然需要往右侧二分，并且不用记录$mid$下标，因为不满足条件。

代码实现：

public static int findLeft(int[] arr, int num) {
    int l = 0, r = arr.length - 1, m = 0;
    int ans = -1;
    while (l <= r) {
        m = l + (r - l) / 2;
        if (arr[m] >= num) {			//区间需要往左侧缩小
            ans = m;					//记录当前的mid下标
            r = m - 1;
        } else {
            l = m + 1;					//右侧二分，不需要记录答案
        }
    }
    return ans;
}

⭐⭐⭐ 在有序数组中找到 <= num的最右位置

也就是说需要的是，在 <= $num$的元素中，最右侧的元素。
同理关键也是二分的方向：
①. 如果$mid$处的元素 <= $num$了，那么$mid$处的元素是不是最右侧呢？不知道，所以需要向右侧二分。同时记录一下答案，万一当前的$mid$处元素就是最右侧的呢。
②. 如果$mid$处的元素 > num，那么只能往左侧二分了，并且不需要记录，因为不符合条件。

❗综上有：
$mid$处元素 <= $num$：向右侧二分，并且记录答案
$mid$处元素 > $num$：向左侧二分，不用记录答案

代码实现

public static int findRight(int[] arr, int num) {
    int l = 0, r = arr.length - 1, m = 0;
    int ans = -1;
    while (l <= r) {
        m = l + (r - l) / 2;
        if (arr[m] <= num) {		//向右侧二分，并且保存答案
            ans = m;
            l = m + 1;
        } else {					//向左侧二分，不用保留答案
            r = m - 1;
        }
    }
    return ans;
}

$🔥🔥🔥$二分搜索不一定发生在有序的数组上（以峰值问题举例）

对于二分搜索的使用场景更加扩展，$不必是有序的数组上$，特定的问题求解也是可以使用二分搜索的。

峰值问题描述
对于一个数组中，如果$i$处的元素都大于$i-1$和$i+1$处的元素，那么$i$处的元素就是一个山峰。并且规定对于$n$长度的数组，$-1$下标与$n$下标处都是一个非常小的值，也就是说$1$下标与$n-1$下标峰值的判断只需要单边判断即可。
现在所求的是数组中有无山峰，有的话任意返回一个山峰的下标即可。

原理思想
首先判断$0$与$n-1$下标处元素，是不是山峰元素，如果是直接返回作为答案就可以结束了。
如果不是山峰元素呢？分开说
对于$0$处元素，如果不是峰值元素，说明$1$的元素必然大于$0$元素，也就是说元素成上升趋势。对于$n-1$下标如果不满足条件，同理可知元素成下降的趋势
对于整个数组，左侧上升趋势，右侧下降趋势，则区间中必然存在山峰（至少一个）。
此时将区间转换到$1$到$n-2$这个区间中，检查中点及其相邻元素的情况。
示例

如果中间元素满足峰值定义，那么就直接返回中间元素。否则根据趋势来进行二分搜索。中间元素左侧成下降趋势，那么必然左边区间有峰值，向左搜索。如果右侧成上升趋势，那么必然是右侧区间有峰值，向右侧搜索（二分法核心展示）。

整体流程

代码实现

// 峰值元素是指其值严格大于左右相邻值的元素
// 给你一个整数数组 nums，已知任何两个相邻的值都不相等
// 找到峰值元素并返回其索引
// 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
// 你可以假设 nums[-1] = nums[n] = 无穷小
// 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
public class Code04_FindPeakElement {

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

		public static int findPeakElement(int[] arr) {
			int n = arr.length;
			if (arr.length == 1) {			//只有一个元素的时候0下标元素就是峰值
				return 0;
			}
			if (arr[0] > arr[1]) {			//判断0下标是否满足
				return 0;
			}
			if (arr[n - 1] > arr[n - 2]) {	//判断n-1下标是否满足
				return n - 1;
			}
			int l = 1, r = n - 2, m = 0, ans = -1;	 //对于区间[1,n-2]进行二分搜索
			while (l <= r) {
				m = (l + r) / 2;
				if (arr[m - 1] > arr[m]) {			//左边整体趋势先上后下，必然有峰值
					r = m - 1;
				} else if (arr[m] < arr[m + 1]) {	//右边整体先上后下，必然有峰值
					l = m + 1;
				} else {	
					ans = m;
					break;
				}
			}
			return ans;
		}

	}

特别的，如果$mid$处的元素整体趋势是凹进去的，那么左右两侧二分都可以：

二分答案法（待续）