Blog of Xingyu Wang
0%

LC周报-二分查找(20221017-20221023)

Posted on Edited on In

前言：

2022 年 3 月初到 2022 年 10 月中旬，我照着 github 用户halfrost编写的 LeetCode 刷题书的知识点顺序，初学了 LeetCode 涉及的基础数据结构和算法。从本周开始，我将按照 LeetCode 网站上的 tag，根据更为细化的知识点顺序，开始新一轮的刷题，预计每周不少于五道题。本系列文章并非完全按照每周完成的题目做的记录，而是阶段性的按照知识点分类组的总结，大致上每周一更，总结 1-2 个知识点，并简单记录该周的刷题进展。

本周做题记录

LC-4、LC-169、LC-240、LC-139、LC-140，涉及知识点二分查找、分治法、记忆化搜索等。

本周总结 1-二分查找

基础

首先回顾对数组vector\<int> nums进行二分查找搜索元素int target的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool BinarySearch(vector<int> nums, int target)
{
    int l = 0, r = nums.size()-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(nums[mid] == target)
            return true;
        else if(nums[mid] < target)
            l =mid + 1;
        else r = mid - 1;
    }
    return false;
}

35 搜索插入位置

原问题实际是要寻找数组中第一个大于target的元素的位置。实现的方式是维护 int 变量ans，初始值设为n，每次满足条件nums[mid]>=target都将对应的mid值记录在ans中。初始值设为n的目的是，若ans一次也未被更新，表明数组中的数值都小于target，则元素应插入在数组最后位置。

关键代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int searchInsert(vector<int>& nums, int target)
{
    int n = nums.size();
    int left = 0;
    int right = n-1;
    int ans = n;
	while(left<=right)
    {
        int mid = (left+right)/2;
        if(nums[mid] >= target)
        {
        right = mid-1;
        ans = mid;
        }
    	else
        left = mid +1;
    }
    return ans;
}

34 数组中搜索元素的第一和最后一个位置

原问题场景为一个具有若干重复元素的数组，给定目标元素值target，返回该元素在数组中出现的第一个位置和最后一个位置。

原问题可转化为如下两个子问题：

  1. 寻找小于target的最大值所在位置\(x\)
  2. 寻找大于target的最小值所在位置\(y\)

原问题的答案即为\(x+1,y-1\)。上述两个子问题的解决思路与 33 题类似，题目核心代码段如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> searchRange(vector<int>& nums, int target)
    {
        int left = binarysearch(nums , target , true);
        int right = binarysearch(nums, target , false)-1;
        if(left <= right && right<nums.size() && left<nums.size() && nums[left] == target && nums[right] == target)
        return {left,right};
        return {-1,-1};
    }

int binarysearch(vector<int>& nums, int target, bool flag)
    {
        int left = 0;
        int right = nums.size()-1;
        int ans = nums.size();
        while(left <=right)
        {
            int mid = (left + right)/2;
            if(nums[mid] > target || (flag ==true && nums[mid]>=target ) )
            {
                right = mid-1;
                ans = mid;
            }
            else left = mid + 1;
        }
        return ans;
    }

33 搜索旋转排序数组

原问题考察将有序数组绕数组中某元素旋转后，二分查找某目标元素的实现。思路是观察旋转后数组中的元素大小，合理设置左右指针的变化即可。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int search(vector<int>& nums, int target)
    {
        int n = nums.size();
        int left = 0;
        int right = n-1;
        int ans = n;
        while(left <= right)
        {
            int mid = (left + right)/2;
            ans = mid;
            if(nums[mid] == target)
            return mid;
            if(nums[0] <= nums[mid] )
            {
                if(target >= nums[0] && target < nums[mid])
                {
                    right = mid-1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
            }
            }
        }
         return -1;
    }

240 搜索二位矩阵

对二维矩阵的每一行进行二分查找即可。

4 寻找两个正序数组中位数

该题为困难题，借用了二分查找的思路，具体如下：假设两数组分别为 A，B，两数组元素总和为\(k\)个，原问题转化为寻找两数组中第\(k/2\)大的数，观察\(A[k/2]\)和\(B[k/2]\)的大小，若\(A[k/2]<B[k/2]\)，则\(A[k/2]\)之前的数也一定不是中位数，原问题就转化为求\(A[k/2..n]\)和\(B\)中第\(k/2\)大的数，直到\(k=1\)，返回数组头即可。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
        int n = nums1.size();
        int m = nums2.size();
        if(n==0)
        return (nums2[(m-1)/2]+nums2[(m)/2])*0.5;
        if(m==0)
        return (nums1[(n-1)/2]+nums1[(n)/2])*0.5;
        int l = (m+n+1)/2;
        int r = (m+n+2)/2;
        int a = getkth(nums1,nums2,0,0,n-1,m-1,l);
        int b = getkth(nums1,nums2,0,0,n-1,m-1,r);
        return (a+b)*0.5;
}

int getkth(vector<int>& nums1, vector<int>& nums2, int start1, int start2, int end1, int end2, int k)
{
        int len1 = end1 - start1 +1;
        int len2 = end2 - start2 +1;
        if(len1 > len2)
        {
            return getkth(nums2, nums1, start2, start1, end2, end1, k);
        }
        if(len1==0)
        return nums2[start2+k-1];
        if(k == 1)
        return min(nums1[start1],nums2[start2]);

        int i = start1 + min(k/2 , len1)-1;
        int j = start2 + min(k/2 , len2)-1;
        if(nums1[i] <= nums2[j])
        {
            return getkth(nums1, nums2, i+1, start2, end1, end2, k-(i-start1+1));
        }
        else
        {
            return getkth(nums1, nums2, start1, j+1, end1, end2, k-(j-start2+1));
        }
}

备注

  1. 对于长度为\(k\)的数组，可不讨论奇偶情况，中位数可统一标识为下标为\((k-1)/2\)和下标为\(k/2\)的元素的平均数。该做法可免去奇偶讨论。