/*
 * @lc app=leetcode.cn id=704 lang=javascript
 *
 * [704] 二分查找
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  // 1. 左闭右闭
  // const len = nums.length;
  // let left = 0;
  // let right = len - 1;

  // while (left <= right) {
  //   // 二分查找需要每次更新左右边界
  //   let mid = (right + left) >> 1
  //   const midVal = nums[mid]
  //   if (target === midVal) return mid

  //   // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1，左边界更新为 mid+1；
  //   // 如果右边界更新为mid，那中间数还在下次查找范围内
  //   if (target > midVal) {
  //     left = mid + 1;
  //   } else {
  //     right = mid - 1;
  //   }
  // }
  // return -1;

  // 2. 左闭右开
  let left = 0;
  let right = nums.length; // 右开
  while (left < right) {
    const midIdx = left + Math.floor((right - left) / 2);
    const mid = nums[midIdx];
    if (mid === target) {
      return midIdx;
    }
    if (mid > target) {
      right = midIdx;
    } else {
      left = midIdx + 1;
    }
  }
  return -1;
};
// @lc code=end

console.log(search([-1, 0, 3, 5, 9, 12], 9))
console.log(search([-1, 0, 3, 5, 9, 12], 2))