前置知识：无
建议：1 会的同学可以跳过，2、3、4 不要跳过
题目
1.在有序数组中确定 num 存在还是不存在
要明确 right 的含义，常见的有：
[left, right][left, right)
// 保证 arr 有序
func exist(arr []int, target int) bool {
n := len(arr)
left, right := 0, n-1 // [left, right]
for left <= right { // 为什么加 =？left、right 指向同一个位置，这个数字也要考虑
mid := left + (right-left)>>1
if arr[mid] > target {
right = mid - 1
} else if arr[mid] < target {
left = mid + 1
} else {
return true
}
}
return false
}// 保证 arr 有序
func exist(arr []int, target int) bool {
n := len(arr)
left, right := 0, n // [left, right)，right 指向有效位置的下一位
for left < right { // 为什么没有 =？left、right 指向同一个位置，right 位置无效，这个数字无效
mid := left + (right-left)>>1
if arr[mid] > target {
right = mid // 为什么没有 -1？ right 指向有效位置的下一位， mid已经判断过了——无效
} else if arr[mid] < target {
left = mid + 1
} else {
return true
}
}
return false
}写代码时要时刻明确 right 的含义，一会儿 ，一会儿 ，一会儿加一，一会儿不加，搞不清楚可能会导致错误的答案或死循环
2.在有序数组中找>=num的最左位置
arr[mid] == target 时，记录答案，但它不一定是最左的位置，所以要继续向左侧二分
// 保证 arr 升序
func GreatEqualMostLeftIdx(arr []int, target int) int {
ans := -1
n := len(arr)
left, right := 0, n // [left, right)
for left < right {
mid := left + (right-left)>>1
if arr[mid] < target {
left = mid + 1
} else {
ans = mid
right = mid
}
}
return ans
}如果是找 <= num 的最左位置呢？
直接看 0 位置，如果 0 位置 <=num，则最左位置是 0；否则是 -1
为啥？因为数组升序
如果是找 > num 的最左位置呢？
3.在有序数组中找<=num 的最右位置
arr[mid] == target 时，记录答案，但它不一定是最右的位置，所以要继续向右侧二分
// 保证 arr 升序
func LessEqualMostRightIdx(arr []int, target int) int {
ans := -1
n := len(arr)
left, right := 0, n // [left, right)
for left < right {
mid := left + (right-left)>>1
if arr[mid] > target {
right = mid
} else {
ans = mid
left = mid + 1
}
}
return ans
}如果是找 < num 的最右位置呢？
4.二分搜索不一定发生在有序数组上
比如 寻找峰值问题
取 mid
mid = (left + right) / 2
其中 left + right 可能会溢出，改写为：left + (right - left) / 2
二分搜索
如果数组长度为 n，那么二分搜索搜索次数是 次，下节课讲时间复杂度，二分搜索时间复杂度 O(logn)
二分搜索不一定发生在有序数组上，只要能确定可以留下（排除）一侧数据即可，即：具有“单调性”
二分答案法
“二分答案法”这个非常重要的算法，很秀很厉害，将在【必备】课程里继续