https://leetcode-cn.com/problems/binary-search/

这道题一看就是用二分查找可以以最小的时间复杂度解决问题

我们定义头尾各一个指针,通过二分他们的中间位,需要注意的一点是不能用 (left+right)/2 去计算他们的中间位,这样有可能会导致number溢出最大值丢失精度

从题意可以理解出这个是升序的数组,所以我们只需要不断二分去取中间位,然后移动left和right就可以得出解了,需要注意的点是移动点之后要移动一位,不然有可能会导致死循环,有可能mid和left和right相等,这样就死循环了

function search(nums: number[], target: number): number {
  let left = 0 ,right = nums.length - 1
  while (left<=right) {
    const mid = left + ((right - left) >>1)
    if (nums[mid] >target) {
      right=mid-1
    } else if(nums[mid] < target){
      left = mid+1
    } else {
      return mid
    }
  }
  return -1
};

空间复杂度O(logn)

时间复杂度O(1)

根据一个大佬的公式写出来的代码

https://www.bilibili.com/video/BV1d54y1q7k7?spm_id_from=333.999.0.0

function search2(nums: number[], target: number): number {
  let l = -1, r = nums.length;
  while (l + 1 !== r) {
    const mid = l + (r - l >> 1)
    if (nums[mid] < target)
      l = mid
    else
      r = mid
  }
  return nums[r] === target ? r : -1
};
Last modification:November 5th, 2021 at 11:21 pm
If you think my article is useful to you, please feel free to appreciate