# 1.二分查找（easy）

TIP

更好的阅读体验应该是：

  1. 审题-思考
  2. 答题
  3. 整理-归纳

# 一、题目

LeetCode：704.二分查找 (opens new window)

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

示例:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

你可以假设 nums  中的所有元素是不重复的。

# 二、二分法解题

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

  • 如果目标值等于中间元素，则找到目标值。
  • 如果目标值较小，继续在左侧搜索。
  • 如果目标值较大，则继续在右侧搜索。

时间复杂度：O(logN)。 空间复杂度：O(1)。

# 三、基础模版I

  1. 确定初始的左右边界:
    • left: 0
    • right: nums.length-1
    • mid: (left + (right - left) >> 1)
  2. 如果中间元素值nums[mid] < target：证明中间值左侧包括中间值都不符合要求，可以直接排除，left = mid + 1
  3. 如果中间元素值nums[mid]：证明中间值右侧包括中间值都不符合要求，可以直接排除，right = mid - 1
  4. 如果中间元素值nums[mid] = target：直接返回mid的下标
  5. 重新定义了左右边界，也需要重新计算中间值，我们需要继续进行范围的排除
  6. 定义搜索的条件，应该是搜索区间都不为空，即left <= right

# 四、Js题解

var search = function(nums, target) {
  let left = 0; // 初始左边界
  let right = nums.length - 1; // 初始右边界
  // 如果left > right 证明整个数组结束了仍没有找到目标值
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2); //防止溢出
    if (target === nums[mid]) {
      return mid;
    } else if (target > nums[mid]) {
      // 目标值大于中值，则中间左侧可以抛弃了
      left = mid + 1;
    } else {
      // 目标值小于中值，则中间右侧可以抛弃了
      right = mid - 1;
    }
  }
  return -1;
};

# 三、写在最后

上面的代码就是二分法模板 I，看过我的二分法总结的同学应该知道，凭借这套模版以及对应的分析，类似的问题应该难不住你了。

如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励

关于我

  • 花名：余光
  • WX：j565017805
  • 沉迷 JS，水平有限，虚心学习中

其他沉淀

Last Updated: 8/6/2021, 6:58:15 PM