每日一道算法题——二分查找

---

开口闭口区分:

开口闭口区分:

• [1,2,3] 左闭右闭
• [1,2,3) 左闭右开
• (1,2,3] 左开右闭

开口如数组(1,2,3)不包含当前数据，也就是指只有2，闭口如数组[1,2,3]表示包含这个数据，也就是指1，2，3
总结：闭口表示包含这个值，开口表示不包含这个值。

---

1、问题

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 - 1。

2、示例

示例 1:
输入: nums = [-1, 0, 3, 5, 9, 12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1, 0, 3, 5, 9, 12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 - 1

3、解决方法

（1）注意点

注意点1: while 循环中是小于等于还是小于

• 左闭右闭，如[1,1]，你不能保证左右闭口值一样，所以两边都闭口 小于等于
• 左闭右开，如[1,1)，如果左闭合和右闭合值一样，这个区间就不是合法的区间，所以左闭右开是小于，其他同理
  总结：两边开口就小于等于，其他情况小于

注意点2 ：循环判断中nums[middle] > target，right是等于 middle -1 还是等于middle

总结：两边闭合就需要middel-1，否则就是middle

（2）代码

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var search = function (nums, target) {let left = 0let right = nums.length// 注意点1: 小于等于还是小于，取决于当前是开口还是闭口// 假设数组[1,1]，这种就不用比较，但你不能保证左右闭口值一样，所以两边都闭口小于等于，其他情况都小于，while (left <= right) {let middle = (nums[left] + nums[right]) / 2 // 中间值（注意边界值，也就是除出了小数的情况）// 注意点2: right = middle -1 还是 = middle if (nums[middle] > target) {right = middle -1 } else if (left < right) {left = middle + 1} else {return middle}return -1}
};