算法随笔 — 搜索查找算法 — 二分查找

水深无声 2022-09-12 03:47 244阅读 0赞

## 二分查找原理 ##

二分查找是应用于 **顺序** 序列的一种算法，在查找的过程中我们在 **保证目标值在查找范围** 的前提下不断 **缩小** 查找范围，最终找到目标值

首先介绍最朴素的二分查找算法，这个算法用于定位给定的目标值，如果找不到则返回 -1

首先要设定头尾两个指针，然后通过中间值 `(head + tail) >> 1` 进行比较，如果中间值和目标值相等则直接返回目标值，否则进行如下操作

\{ a r r \[ m i d \] < x ， h e a d = m i d + 1 a r r \[ m i d \] > x ， t a i l = m i d − 1 \\begin\{cases\} arr\[mid\]<x，head=mid+1 \\\\ arr\[mid\] > x，tail = mid - 1 \\end\{cases\} \{ arr\[mid\]<x，head=mid\+1arr\[mid\]>x，tail=mid−1

这里的操作很容易想明白，目标是为了保证目标在查找范围内缩小查找范围

![二分查找缩小范围][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Zu25byP5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16]

function binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h <= t) { 
            mid = (t + h) >> 1
            if (nums[mid] === target) return mid
            if (nums[mid] < target) h = mid + 1
            else t = mid - 1
        }
        return -1
    }

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

## 01模型 ##

00001111

这个模型通常用来找 `最后一个0` 和 `第一个1`

这里的 `最后一个0` 可以理解为 **最后一个小于等于x** 的值;  
而 `第一个1` 可以理解为 **第一个大于等于x** 的值。

这里以 查找第一个大于等于x的值为例 进行推理

// 01-1 核心部分
    while (h < t) { 
    	// 中间指针
        mid = (h + t) >> 1
        // 范围缩小选择
        if (nums[mid] <= target) h = mid
        else t = mid - 1
    }

![01-1][]

// 01-1 核心代码
    function b_binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = (h + t) >> 1
            // mid = h + ((t - h) >> 1)
            if (nums[mid] >= target) t = mid
            else h = mid + 1
        }
        return h
    }

同理得出 `01-0` 代码

// 01-0 核心代码
    function s_binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = h + ((t - h) >> 1) + 1  // 无论什么情况都往右偏一位
            // parseInt(`${(h + t + 1) / 2}`) // 奇数时找到中间值，偶数时找到中间偏右
            if (nums[mid] <= target) h = mid
            else t = mid - 1
        }
        return h
    }

**中间指针的偏向**

在上面的代码中可以发现 `01-0` 和 `01-1` 的 `mid` 有细微的差别

在搜索序列中如果元素个数是奇数的话，二者定位到的中间值是一样的；但如果是偶数， `01-0` 定位到的是中间偏右的值，而 `01-1` 定位到的是中间偏左的值

如果是右偏的话，有两种情况

1.  如上所述，奇数时定位到正中间，偶数时定位到中间偏右的数字
    
        mid = parseInt(`${ (h + t + 1) / 2}`)
2.  指针均向右偏一位
    
        mid = ((h + t) >> 1) + 1
        mid = h + ((t - h) >> 1) + 1 // 在静态语言中，这种写法可以防止溢出

这两种情况都是行得通的

![指针偏向原理][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Zu25byP5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 1]

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

## 二分查找题目 ##

> ### leetCode 69 x的平方根 ###

![leetCode69题目][leetCode69]  
这道题可以转化为 **查找最后一个小于等于x的值**

function mySqrt(x: number): number { 
        let h = 0, t = x, mid: number
        while (h < t) { 
            mid = ((h + t) >> 1) + 1
            if (mid ** 2 <= x) h = mid
            else t = mid - 1
        }
        return h
    }

![leetCode69结果][leetCode69 1]

> ### leetCode 35 搜索插入位置 ###

![leetCode35题目][leetCode35]  
这道题找到 **第一个大于等于x** 的位置即可

function searchInsert(nums: number[], target: number): number { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = (h + t) >> 1
            if (nums[mid] >= target) t = mid
            else h = mid + 1
        }
        return (h === nums.length - 1 && nums[h] < target) ? h + 1 : h
    }

![leetCode35结果][leetCode35 1]

> ### leetCode 1 两数之和 ###

![leetCode1题目][leetCode1]  
这道题我们用朴素的二分查找精准找到目标值

首先遍历数组，然后在后面找到  t a r g e t − x target - x target−x 的值

![leetCode1解析][leetCode1 1]  
**注意**，二分查找的前提是针对有序序列，因此我们得先对原数组进行排序，这里我们使用之前学过的归并排序

type dataType = [val: number, ind: number]
    function binarySearch (nums: dataType[], l: number, target: number) { 
        let h = l, t = nums.length - 1, mid: number
        while (h <= t) { 
            mid = (h + t) >> 1
            if (nums[mid][0] === target) return nums[mid][1]
            if (nums[mid][0] < target) h = mid + 1
            else t = mid - 1
        }
        return -1
    }
    function twoSum(nums: number[], target: number): number[] { 
        const data: dataType[] = [], ret: number[] = []
        let ind: number
        nums.forEach((val, i) => data.push([val, i]))
        mergeSort(data, 0, nums.length - 1)
        for (let i = 0; i < data.length - 1; i++) { 
            ind = binarySearch(data, i + 1, target - data[i][0])
            if (ind > -1) ret.push(data[i][1], ind)
        }
        return ret
    }
    //* 归并排序
    function mergeSort (data: dataType[], l: number, r: number) { 
        if (l >= r) return
        const mid = (l + r) >> 1
        mergeSort(data, l, mid)
        mergeSort(data, mid + 1, r)
        const temp: dataType[] = []
        let p1 = l, p2 = mid + 1
        while (p1 <= mid || p2 <= r) { 
            if (p2 > r || (p1 <= mid && data[p1][0] < data[p2][0])) temp.push(data[p1++])
            else temp.push(data[p2++])
        }
        temp.forEach((v, i) => data[l + i] = v)
    }

![leetCode1结果][leetCode1 2]  
当然这里如果是用C++，通过符号重载的方式使用 sort 效率会更高

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

![leetCode34题目][leetCode34]  
这道题就是 01模型 运用的典型例题了

找到元素的第一个位置，就是 01-1，找到最后一个位置就是 01-0

//* 01-0
    function s_binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = ((h + t) >> 1) + 1
            if (nums[mid] <= target) h = mid
            else t = mid - 1
        }
        //* 找第二个值的时候已经可以肯定场上肯定存在目标值
        return h
    }
    //* 01-1
    function b_binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = (h + t) >> 1
            if (nums[mid] >= target) t = mid
            else h = mid + 1
        }
        return nums[h] === target ? h : -1
    }
    function searchRange(nums: number[], target: number): number[] { 
        let fir: number, sec: number
        fir = b_binarySearch(nums, target)
        if (fir === -1) return [-1, -1]
        sec = s_binarySearch(nums, target)
        return [fir, sec]
    }

主程序的思路也很简单，如果找不到目标值第一次出现位置就直接返回 `[-1, -1]`，否则就继续找最后一次出现位置(二者是可以重合的)

![leetCode34结果][leetCode34 1]

> ### leetCode 1658 将x减到0的最小操作数 ###

![leetCode1658题目][leetCode1658]  
这道题给人一种很直观的解决办法就是首先统计左右两个方向的前缀和，在遍历左前缀和的时候利用二分作用于右前缀和数组，找出 `x - sums[l]`

但是这道题只要计算一次从左到右的前缀和即可

![leetCode1658解析1][leetCode1658_1]

这里强调一下，之前我们学习的区间和如下：  
 s \[ 4 \] − s \[ 2 \] = n \[ 2 \] + n \[ 3 \] 即 s \[ i \] − s \[ j \] = ∑ n = j n = i − 1 a n s\[4\] - s\[2\] = n\[2\]+n\[3\]\\\\ 即 s\[i\]-s\[j\]=\\sum\_\{n=j\}^\{n=i-1\}a\_n s\[4\]−s\[2\]=n\[2\]\+n\[3\]即s\[i\]−s\[j\]=n=j∑n=i−1an

而这里使用的  n \[ i \] − s \[ j \] n\[i\]-s\[j\] n\[i\]−s\[j\] 相当于统计  ( j , i ) (j, i) (j,i) 之间的元素数量

![leetCode1658解析2][leetCode1658_2]  
因此当找到 i 和 j 后，结果就是  c n t = n u m s . l e n g t h − ( i − j ) cnt = nums.length - (i - j) cnt=nums.length−(i−j)

function binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h <= t) { 
            mid = (h + t) >> 1
            if (nums[mid] === target) return mid
            if (nums[mid] < target) h = mid + 1
            else t = mid - 1
        }
        return -1
    }
    function minOperations(nums: number[], x: number): number { 
        //* 构建前缀和数组
        const sums = [0]
        nums.forEach((n, i) => sums.push(n + sums[i]))
        //* 左右计数
        let j: number, cnt: number, ans = -1
        for (let i = nums.length, s = 0; i >= 0; --i, s += nums[Math.max(i, 0)]) { 
            j = binarySearch(sums, x - s)
            if (j === -1) continue
            cnt = nums.length - (i - j)
            if (cnt > nums.length) continue // 当i<=j的时候会发生这种情况
            if (ans === -1 || cnt < ans) ans = cnt
        }
        return ans
    }

这里的主函数策略是，每次循环的时候先从前缀和中看有没有目标值(x - s)，没有的话就继续下一循环  
![1658结果][1658]

> ### leetCode 475 供暖器 ###

![475题目][475]  
这道题思路很简单，首先给供暖器地址排序(二分查找的前提)，然后遍历房子，找到里自己最近供暖器的位置并记录距离

最后，距离最大的值即最小范围

//* 01-0
    function s_binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = ((h + t) >> 1) + 1
            if (nums[mid] <= target) h = mid
            else t = mid - 1
        }
        return nums[h]
    }
    //* 01-1
    function b_binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = (h + t) >> 1
            if (nums[mid] >= target) t = mid
            else h = mid + 1
        }
        return nums[h]
    }
    function findRadius(houses: number[], heaters: number[]): number { 
        heaters = heaters.sort((i, j) => i - j)
        let maxRadius = -1, recentHeater: number
        houses.forEach(house => { 
            recentHeater = Math.min(Math.abs(house - s_binarySearch(heaters, house)), Math.abs(b_binarySearch(heaters, house) - house))
            maxRadius = Math.max(maxRadius, recentHeater)
        })
        return maxRadius
    }

![475结果1][475_1]  
这里的做法是使用了 01模型 的两种结构，但是如果对 01模型 掌握足够深的话，只要用一种即可

function b_binarySearch (nums: number[], target: number) { 
        let h = 0, t = nums.length - 1, mid: number
        while (h < t) { 
            mid = (h + t) >> 1
            if (nums[mid] >= target) t = mid
            else h = mid + 1
        }
        return h
    }
    function findRadius(houses: number[], heaters: number[]): number { 
        heaters = heaters.sort((i, j) => i - j)
        let maxRadius = -1, a: number, b: number, ind: number
        houses.forEach(house => { 
            ind = b_binarySearch(heaters, house)
            a = Math.abs(heaters[ind] - house)
            b = Math.abs(ind ? heaters[ind - 1] - house : a + 1)
            maxRadius = Math.max(maxRadius, Math.min(a, b))
        })
        return maxRadius
    }

这里的思路是首先找到在当前房子后面的供暖器(`01-1`)，如果该供暖器不是第一个，就和该供暖器的上一个比较谁离房子更近

通过这道题我们可以发现，如果01模型找不到结果(比如说 01-1 找不到大于等于目标值的值)，就会返回第一个元素下标

![475结果2][475_2]  
可以看到结果同样是正确的

> ### leetCode 81 搜索旋转排序数组II ###

![81题目][81]  
这道题读起来很复杂，但是实际情况如下图所示  
![81解析][81 1]  
每次取中间值的时候都只和头部/尾部进行对比，如果在非阴影区域，则只要将两边指针继续往中间靠

因为本题的特殊性，需要4个指针

有两个固定在头尾，另外两个就是逐渐缩小的区间

function search(nums: number[], target: number): boolean { 
        if (!nums.length) return false
        if (nums[0] === target || nums[nums.length - 1] === target) return true
        //* 设定两区间的头和尾
        let l = 0, r = nums.length - 1
        while (l < r && nums[l] === nums[0]) l++
        while (l < r && nums[r] === nums[nums.length - 1]) r--
        const head = l, tail = r
        //* 定位元素
        let mid: number
        while (l <= r) { 
            mid = (l + r) >> 1
            if (nums[mid] === target) return true
            //* 假如在右区间
            if (nums[mid] < nums[tail]) { 
                if (nums[mid] < target && target <= nums[tail]) l = mid + 1
                else r = mid - 1
            } else { 
                //* 在左区间
                if (nums[head] <= target && target < nums[mid]) r = mid - 1
                else l = mid + 1
            }
        }
        return false
    }

![81结果][81 2]

> ### leetCode 4 寻找两个正序数组的中位数 ###

![4题目][4]  
要解决这道题首先要有一个共识  
![4解析][4 1]  
有了此共识之后我们就可以开始编码了

function findK (nums1: number[], nums2: number[], l1: number, l2: number, k: number): number { 
        //* 边界条件判断
        if (l1 === nums1.length) return nums2[l2 + k - 1]
        if (l2 === nums2.length) return nums1[l1 + k - 1]
        if (k === 1) return nums1[l1] < nums2[l2] ? nums1[l1] : nums2[l2]
        //* 从两数组中取值的处理
        let cnt1 = Math.min(k >> 1, nums1.length - l1)
        let cnt2 = Math.min(k - cnt1, nums2.length - l2)
        //* 缩小范围
        if (nums1[l1 + cnt1 - 1] < nums2[l2 + cnt2 - 1]) { 
            return findK(nums1, nums2, l1 + cnt1, l2, k - cnt1)
        }
        return findK(nums1, nums2, l1, l2 + cnt2, k - cnt2)
    }
    function findMedianSortedArrays(nums1: number[], nums2: number[]): number { 
        const cnt = nums1.length + nums2.length, mid = (nums1.length + nums2.length + 1) >> 1
        const a = findK(nums1, nums2, 0, 0, mid)
        if (cnt % 2) return a
        const b = findK(nums1, nums2, 0, 0, mid + 1)
        return (a + b) / 2
    }

首先设定一个可以在两个数组中找到第k个元素的函数，如果两个操作数组的长度是奇数，则说明中间的那个值就是中间数；如果是偶数，则需要找到偏右的数字并求平均

这里的边界条件也很好理解，当其中一个数组为空时就相当于是直接对另一个数组进行操作；当k为1时，只需要比较两个数组的头部元素看谁更小

从两个数组中取值时需要注意，数组的长度可能不够  k 2 \\frac\{k\}\{2\} 2k，因此需要做一下兼容处理

最后的缩小范围操作就是基于刚刚提到的共识进行操作的

这道题虽然编码上不像传统的二分查找，但是思想上是一样的

二分查找通过中间值的比较来确定目标值，而这里通过3个边界条件来确定目标值；  
二分查找通过左右指针来缩小范围，这里通过计数和头部指针来缩小范围。

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

熹微~

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Zu25byP5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/dc128cc8856c4e0e9621e951f376d762.png
[01-1]: /images/20220828/bc9aaae55104433dbdff6b1c8bdc5f50.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Zu25byP5aSn5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/08fbc7376d1a47a1bbcbffc769851723.png
[leetCode69]: /images/20220828/235ab0481e99418f96ee4fe28aabec71.png
[leetCode69 1]: /images/20220828/8fd846b9571545fc847f8356399d19cf.png
[leetCode35]: /images/20220828/1153ab6f9f194671815084dac7a4934d.png
[leetCode35 1]: /images/20220828/2438ab2aa27243e38326768842b107a7.png
[leetCode1]: /images/20220828/2a500687202940df9475aac97aaa8960.png
[leetCode1 1]: /images/20220828/7546b06f0f374effbcf1577bd90e6ca3.png
[leetCode1 2]: /images/20220828/7f38c457783a4c088eb0e66e90d6facc.png
[leetCode34]: /images/20220828/d7ac136c7a1f4231ab89b39f1a3dc430.png
[leetCode34 1]: /images/20220828/296c990339264acdbaf764baea1da408.png
[leetCode1658]: /images/20220828/e7c2a7d43c3b4866b71ed6a2921e6368.png
[leetCode1658_1]: /images/20220828/a73c791c38e54b788d659b3da986ae15.png
[leetCode1658_2]: /images/20220828/1d1845330acb427dac8454774f689bd6.png
[1658]: /images/20220828/8432cfbb60d64501add87ece2559e0bd.png
[475]: /images/20220828/d21c778653164b84a361032ae04b5ad1.png
[475_1]: /images/20220828/6154c9495ad54cbd9931662bffe67df4.png
[475_2]: /images/20220828/ac35b903a71e44a0bb9104dc039e5a1f.png
[81]: /images/20220828/bb3f99715b4d46a68f1c0b5cd0ebf92b.png
[81 1]: /images/20220828/b3feb37f63d0495f9201dc71b3db9b62.png
[81 2]: /images/20220828/0793597b49ad41e7a317cea1ed106a44.png
[4]: /images/20220828/3d9e96caef29466a840bcf32512af87a.png
[4 1]: /images/20220828/47cf18b95c02491490efd2d99dd58185.png