算法 - 二分搜索法 / 二分法(704)

2023-12-13 04:40:46

原理:

利用数组的有序性,每次取查找范围的中间点,缩窄一半的查找空间。比较中间值和目标值的大小,直到找到目标值或者查找区间为空时返回。?

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目:?

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

示例 1:

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

提示:

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

思路:

二分法的前提条件:数组为有序数组,且?数组中无重复元素;

因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的;

注意:区间的定义问题

区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即 [left, right],或者左闭右开即 [left, right)。

方法一:?左闭右闭?[left, right]

      /**
       * @param {number[]} nums
       * @param {number} target
       * @return {number}
       */
      var search = function (nums, target) {
        // right是数组最后一个数的下标,num[right]在查找范围内,是左闭右闭区间
        let mid = 0,
          left = 0,
          right = nums.length - 1;
        // 当left=right时,由于nums[right]在查找范围内,所以要包括此情况
        while (left <= right) {
          mid = Math.floor((left + right) / 2);
          let middleVal = nums[mid];
          // 如果中间数大于目标值,要把中间数排除查找范围,所以右边界更新为mid-1;
          // 如果右边界更新为mid,那中间数还在下次查找范围内
          if (middleVal < target) {
            left = mid + 1;
          } else if (middleVal > target) {
            right = mid - 1;
          } else {
            return mid;
          }
        }
        return -1;
      };

方法二:?左闭右开?[left, right)

      /**
       * @param {number[]} nums
       * @param {number} target
       * @return {number}
       */
      console.log(new Date().getTime());
      var search = function (nums, target) {
        let mid = 0,
          left = 0,
          right = nums.length;
        while (left < right) {
          mid = Math.floor((left + right) / 2);
          let middleVal = nums[mid];
          if (middleVal < target) {
            left = mid + 1;
          } else if (middleVal > target) {
            right = mid;
          } else {
            return mid;
          }
        }
        return -1;
      };

视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili

文章来源:https://blog.csdn.net/qq_38290251/article/details/134920878
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。