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

概述

https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

暴力遍历

O(n) 的时间复杂度。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int count = 0;
        for (auto n : nums) {
            if (n == target) {
                count ++;
            } else {
                if (count != 0) break;
            }
        }
        return count;
    }
};

二分查找

求出左右边界计算差值即可。

由于这里是算差值，所以我们也不需要考虑越界的情况。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int m = (r - l) / 2 + l;
            if (nums[m] == target) {
                r = m - 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else { // nums[m] > target
                r = m - 1;
            }
        }
        int lb = l;
        l = 0, r = nums.size() - 1;
        while (l <= r) {
            int m = (r - l) / 2 + l;
            if (nums[m] == target) {
                l = m + 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else { // nums[m] > target
                r = m - 1;
            }
        }
        int rb = l;
        return rb - lb;
    }
};

Links: sword-offer-53-1

未经允许，禁止转载，本文源站链接：https://iamazing.cn/