34-查找元素/35-搜索插入位置

LeetCode 34. Find First and Last Position of Element in Sorted Array

LeetCode-34

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with $O(logn)$ runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

二分模板

模板一：找最左边的元素

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

模板二：找最右边的元素

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

method: 两次二分

一次找大于等于target的最小值
一次找小于等于target的最大值

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res{-1, -1};
    if (nums.size() == 0) return res;
    // 第一次：找大于等于target的最小数
    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;
    }
    res[0] = nums[l] == target ? l : -1;

    // 第二次：找小于等于target的最大数
    r = nums.size() - 1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (nums[mid] <= target) l = mid;
        else r = mid - 1;
    }
    res[1] = nums[r] == target ? r : -1;
    return res;
}

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

---

LeetCode 35. Search Insert Position

LeetCode-35

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with $O(logn)$ runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 7
Output: 4

method: 二分模板一

找大于等于target的最小数，用模板一不会越界
用模板二，当l指向nums.size() - 1，r指向nums.size()的时候，mid = nums.size()，此时上取整越界

int searchInsert(vector<int>& nums, int target) {
    int l = 0, r = nums.size(); // 可能找到最后一个元素的下一个位置
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return r;
}

时间复杂度：$O(logn)$
空间复杂度：$O(1)$