二分查找

算法 评论

二分查找

二分的两段性

二分.png

注：

设计一个check函数，

  • 如果函数的性质满足绿色部分，不满足红色部分，使用模板一。
  • 如果函数的性质满足红色部分，不满足绿色部分，使用模板二。

模板一：

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

模板二：

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

二分的流程

  1. 确定二分边界
  2. 编写代码框架
  3. 设计一个check（性质） 设计完的check函数，答案一定要在性质的边界
  4. 判断区间如何更新
  5. 如果更新方式写的是l = mid, r = mid - 1，那么就在算mid的时候加上1（即模板2）

例题

leetcode69

显而易见这里要求向下取整，check函数为：t² <= x，

  • 在根号t左边，即红色部分满足这个性质

  • 在根号t右边，即绿色部分不满足这个性质，

故使用模板二。

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = l + (long long)r + 1 >> 1;
            if (mid <= x / mid) {   //等价于mid * mid <= x，防止溢出
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

leetcode35

这里check函数使用向上取整，即满足绿色部分，不满足红色部分，使用模板一。

class Solution {
public:
    int searchInsert(vector& nums, int target) {

        // 边界条件
        if(nums.empty() || nums.back() < target) {
            return nums.size();
        }

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

leetcode34

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        if (nums.empty()) {
            return {-1, -1};
        }

        int start, end;
        int l = 0, r = nums.size() - 1;

        // 起始位置：大于等于target的第一个数 
        // check():nums[mid] >= target  绿色部分满足，红色不满足  模板一
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return {-1, -1};
        } else {
            start = l;
        }

        l = 0, r = nums.size() - 1;

        // 终止位置：小于等于target的最后一个数
        // check():nums[mid] <= target 红色部分满足，绿色不满足  模板二
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (nums[l] != target) {
            return {-1, -1};
        } else {
            end = l;
        }

        return {start, end};
    }
};

leetcode74

公式：把二维数组的编号k变成(i, j)的形式：

matrix[k / n] [k % n] n为二维数组的列数。

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }
        int m = matrix.size(), n = matrix[0].size();
        int l = 0, r = m * n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid / n][mid % n] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (matrix[l / n][l % n] == target) {
            return true;
        } else {
            return false;
        }
    }
};

leetcode153

该题旋转数组把数组分为两段。

设计的check函数满足绿色而不满足红色，且答案恰好在端点处。

class Solution {
public:
    int findMin(vector& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] <= nums.back()) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
};

leetcode33

对于这类旋转数组，可以先找出最小值的点，进而找出两段有序数组。

class Solution {
public:
    int search(vector& nums, int target) {
        int l = 0, r = nums.size() - 1;

        // 找到最小值
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] <= nums.back()) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // 判断target在哪一段
        if (target <= nums.back()) {
            r = nums.size() - 1;
        } else {
            l = 0;
            r = r - 1;
        }

        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        if (nums[l] != target) {
            return -1;
        } else {
            return l;
        }
    }
};

leetcode278

满足是坏版本的第一个数，模板一。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + (long long)r >> 1;
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

leetcode162（该题不适用模板）

class Solution {
public:
    int findPeakElement(vector& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

leetcode287（该题不适用模板）

本题可根据抽屉原理做。有n + 1个苹果但只有n个抽屉，那么把抽屉分为两部分：(l, mid)和(mid + 1, r)，必定会有一边苹果的个数大于抽屉的个数。

同样的，把数组从中间一分为二，则必定有一边所包含元素的个数大于这一边区间的长度。

class Solution {
public:
    int findDuplicate(vector& nums) {
        int n = nums.size() - 1;
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            // 统计左边元素个数
            int cnt = 0;
            for (auto i : nums) {
                if (i >= l && i <= mid) {
                    cnt++;
                }
            }
            //如果左边“苹果”个数大于“抽屉”个数，则答案在左边
            if (cnt > mid - l + 1) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

leetcode275

class Solution {
public:
    int hIndex(vector& citations) {
        int l = 0, r = citations.size();
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (citations[citations.size() - mid] >= mid) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

zyBack-end developer

个人简介。