#二分查找

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

示例 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

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

#解题思路

题目信息：升序，不重复

#思路一

首先，考虑暴力解法，循环遍历 nums 直到找到 target，复杂度为 O(n)

#思路二

其次可以想到双指针法，左右指针同时向中间遍历，复杂度依旧为 O(n)，还需要优化

#思路三

最后就是二分查找法，因为升序不重复，结合双指针，可以根据双指针中间的元素大小与 target 对比来跳过一半的元素，每次查找区间为 n,n/2,n/4,n/2^k，直到 n/2^k=1，则 k=log(2)n，复杂度为 O(logn)，所以用二分查找

还要考虑到区间的开闭问题，这里我选择了左闭右闭情况，感觉更符合直觉

#首次代码

function search(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1
  let mid: number

  // 左闭右闭时左右可以相等
  while (left <= right) {
    // 小数舍去
    mid = Math.floor(left + (right - left) / 2)
    // 找到直接返回
    if (nums[mid] === target) {
      return mid
    } else if (nums[mid] < target) {
      // nums[mid]肯定不等于target所以可以+1
      left = mid + 1
    } else {
      // nums[mid]肯定不等于target所以可以-1
      right = mid - 1
    }
  }

  // 找不到返回-1
  return -1
}