Search

二分查找

二分查找是最基础的查找算法，它的时间复杂度为 O(logn)。虽然二分查找的思想简单直白，但是写二分查找的时候在处理边界条件的时候会写错。这里给出一种处理边界条件的时候不容易写错的二分查找模板。参考视频讲解


function search(nums: number[], target: number): number {
  function binarySearch(l: number, r: number): number {
    while (l + 1 !== r) {
      const mid = Math.floor((l + r) / 2);
      const tmp = nums[mid];
      if (tmp > target) {
        r = mid;
      } else if (tmp < target) {
        l = mid;
      } else {
        return mid;
      }
    }
    return -1;
  }
  // 这里必须是 -1 和 nums.length
  return binarySearch(-1, nums.length);
}