算法入门之二分查找

099057a3a19aa5000022d31e9554566e.jpg

704. 二分查找

原题链接：https://leetcode-cn.com/problems/binary-search/

在升序数组 nums 中寻找目标值 target，对于特定下标 i，比较 nums[i] 和 target 的大小：

如果 nums[i]=target，则下标 ii 即为要寻找的下标；

如果 nums[i]>target，则 target 只可能在下标 i 的左侧；

如果 nums[i]<target，则 target 只可能在下标 i 的右侧。

二分查找的做法是，定义查找的范围 [left,right]，初始查找范围是整个数组。每次取查找范围的中点 mid，比较 nums[mid] 和 target 的大小，如果相等则，mid 即为要寻找的下标，如果不相等则根据 nums[mid] 和 target 的大小关系将查找范围缩小一半。

由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 O(logn)，其中 n 是数组的长度。

二分查找的条件是查找范围不为空，即 left≤right。如果 target 在数组中，二分查找可以保证找到 target，返回 target 在数组中的下标。如果 target 不在数组中，则当 left>right 时结束查找，返回 −1。

var search = function (nums, target) {
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    let mid = parseInt(left + (right - left) / 2)
    if (target === nums[mid]) {
      return mid
    } else if (target > nums[mid]) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
};

278. 第一个错误的版本

原题链接：https://leetcode-cn.com/problems/first-bad-version/

var solution = function (isBadVersion) {
  return function (n) {
    let left = 1, right = n;
    while (left < right) { // 循环直至区间左右端点相同
      const mid = Math.floor(left + (right - left) / 2); // 防止计算时溢出
      if (isBadVersion(mid)) {
        right = mid; // 答案在区间 [left, mid] 中
      } else {
        left = mid + 1; // 答案在区间 [mid+1, right] 中
      }
    }
    // 此时有 left === right，区间缩为一个点，即为答案
    return left;
  };
};

35. 搜索插入位置

原题链接：https://leetcode-cn.com/problems/search-insert-position/

var searchInsert = function (nums, target) {
 const n = nums.length;
 let left = 0, right = n - 1, ans = n;
 while (left <= right) {
   let mid = parseInt(left + (right - left) / 2);
   if (target <= nums[mid]) {
     ans = mid;
     right = mid - 1;
   } else {
     left = mid + 1;
   }
 }
 return ans;
};

69. x 的平方根

原题链接：https://leetcode-cn.com/problems/sqrtx/

var mySqrt = function (x) {
  let left = 0
  let right = x
  let mid = parseInt(left + (right - left) / 2)
  while (left <= right) {
    if (mid ** 2 === x) {
      return mid
    } else if (mid ** 2 > x) {
      right = mid - 1
    } else {
      left = mid + 1
    }
    mid = parseInt(left + (right - left) / 2)
  }
  return mid
};

34. 在排序数组中查找元素的第一个和最后一个位置

原题链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

var searchRange = function(nums, target) {
    let left = 0
    let right = nums.length - 1
    let start = -1
    let end = -1

    while(left <= right) {
        if (nums[left] < target) left++
        if (nums[left] === target && start === -1) start = left++
        if (nums[right] > target) right--
        if (nums[right] === target && end === -1) end = right--
        if(start > -1 && end > -1) break
    }
    return [start, end]
};