- 时间复杂度：
O(log n)，空间复杂度：O(1) - 适用的前提条件：有序数组
- 难点：区间范围，一般有两种：左闭右闭
[left, right]，左闭右开[left, right) - 遵循原则：循环不变量，即每次循环的范围需要一开始就确定好
如果是左闭右闭，那么：
left = 0，right = arr.length - 1，因为 right 要能够访问到while (left <= right)要使用 ⇐ ，因为 left == right 是有意义的，所以使用 ⇐if (nums[middle] > target)right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1。反之 left 也要赋值为 middle + 1
左闭右闭：
const search = function(nums, target) {
let left = 0
let right = nums.length - 1 // right是数组最后一个数的下标，nums[right]在查找范围内，是左闭右闭区间
while (left <= right) { // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
let middle = left + ((right - left) >> 1) // 位运算 防止大数溢出
if (nums[middle] > target) { // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为middle-1，如果右边界更新为middle，那中间数还在下次查找范围内
right = middle - 1 // 去左面闭区间寻找
} else if (nums[middle] < target) {
left = middle + 1 // 去右面闭区间寻找
} else {
return middle
}
}
return -1
}左闭右开：
const search = function(nums, target) {
let left = 0
let right = nums.length // right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间
while (left < right) { // 当left=right时，由于nums[right]不在查找范围，所以不必包括此情况
let middle = left + ((right - left) >> 1)
// 如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应在；
// 由于right本来就不在查找范围内，所以将右边界更新为中间值，
// 如果更新右边界为middle-1则将中间值的前一个值也踢出了下次寻找范围，所以不行
if (nums[middle] > target) {
right = middle
} else if (nums[middle] < target) {
left = middle + 1
} else {
return middle
}
}
return -1
}leetcode：
- 35. 搜索插入位置 - 力扣（LeetCode） （返回的 left 就是第一个大于等于 target 的位置）
- 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） （基于 35 题扩展）
- 162. 寻找峰值 - 力扣（LeetCode） （变化点：mid 不与 target 进行比较，与相邻数比较）
- 153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode） （变化点：mid 不与 target 进行比较，与右边界比较）
- 33. 搜索旋转排序数组 - 力扣（LeetCode） （变化点：mid 不与 target 进行比较，与左边界比较）