LeetCode - 704 二分查找

朴灿烈づ我的快乐病毒、 2023-10-01 09:55 75阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目分析

--------------------

### 题目来源 ###

[704. 二分查找 - 力扣（LeetCode）][704. _ - _LeetCode]

### 题目描述 ###

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

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>nums = [-1,0,3,5,9,12], target = 9</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>解释</td> 
   <td>9 出现在 nums 中并且下标为 4</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>nums = [-1,0,3,5,9,12], target = 2</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>-1</td> 
  </tr> 
  <tr> 
   <td>解释</td> 
   <td>2 不存在 nums 中因此返回 -1</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

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

### 题目分析 ###

这一题过一遍，我脑子第一个想法是根据值找索引，那不就是map吗，直接根据元素哈希O(1)查找不香吗？

var search = function(nums, target) {
        const map = new Map()
        nums.forEach((item,index)=>map.set(item,index))
        const result = map.get(target)
        return typeof result === 'undefined' ? -1 : result
    }

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LyP5Z-O5LmL5aSW_size_20_color_FFFFFF_t_70_g_se_x_16][]虽然结果正确，但是内存消耗很大，执行用时也不是很理想

内存消耗过大的原因应该是：将数组元素 转移到 map中，相当于拷贝一份，并且map的内存消耗要比数组多，因为map是双列的，且哈希表本身就是比数组复杂。

另外执行用时长的原因应该是浪费在了forEach遍历数组元素上了O(n)，遍历一次都可以找到了。

以上数组转map，来实现值找索引，优势在于数组乱序，一次转完map后，多次查找，如果只是单纯的一次查找后就废弃，性能确实不高。

那么在看看题目，发现nums数组是升序的，所以二分查找 O(logN)的时间复杂度是小于上面的方式的。

var search = function(nums, target) {
        let start = 0, end = nums.length -1
        
        while(start <= end) {
            const mid = start + Math.floor((end - start) / 2)
            const num = nums[mid]
            if(target === num) {
                return mid
            } else if(target > num) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    
        return -1
    }

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LyP5Z-O5LmL5aSW_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

使用二分查找后，在执行用时和内存消耗上都超过了使用map，但是二分查找的局限性太大，只能在有序的数组中查找，如果是一个乱序的数组，将其变得有序，也需要耗费不少时间。

在上面二分查找的代码中，需要注意的其实就一处：mid的值计算，这里有两个点需要注意

1、值溢出

即不能写成 Math.floor((start + end) / 2)，如果刚好start + end 超过了最大值限制，就发生值溢出

2、JS除法结果不是整数，而是小数

受到Java的影响 意味 int / int 结果还是 int，但是JS中没有int类型，整数与整数相除也会得到小数，所以需要对结果取整，这里其实向上取整，向下取整都可以，上面代码是向下取整，我们再来试试向上取整

var search = function(nums, target) {
        let start = 0, end = nums.length -1
        
        while(start <= end) {
            const mid = start + Math.ceil((end - start) / 2)
            const num = nums[mid]
            if(target === num) {
                return mid
            } else if(target > num) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    
        return -1
    }

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LyP5Z-O5LmL5aSW_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

性能上也没差多少

[704. _ - _LeetCode]: https://leetcode.cn/problems/binary-search/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LyP5Z-O5LmL5aSW_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1794c3925f6b4a839edcb5b26db39cfc.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LyP5Z-O5LmL5aSW,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LyP5Z-O5LmL5aSW_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/3839de44a3fd407391674b0743022e46.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LyP5Z-O5LmL5aSW,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LyP5Z-O5LmL5aSW_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/66987dba71174f1dbe4a24d5dfdee14f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LyP5Z-O5LmL5aSW,size_20,color_FFFFFF,t_70,g_se,x_16