Leetcode题解 剑指 Offer 53 - I. 在排序数组中查找数字 I

PROBLEM

剑指 Offer 53 - I. 在排序数组中查找数字 I

剑指 Offer 53 - II. 0～n-1中缺失的数字

难度 简单

MY ANSWER

二分，时间复杂度O(logn)，空间复杂度O(1)。

BETTER SOLUTION

贴一下简洁代码。

调用两次二分查找第一个比target大的索引，最后一个比target小的索引。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0; j = nums.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
};

二分查找第一个索引与值不相等的位置。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i = 0, j = nums.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
};

SUMMARY

掌握二分。