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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return 0;

        if (nums.size() == 1) return nums[0] == target ? 1 : 0;

        int left = lowwer_bound(nums, target);
        int right = upper_bound(nums, target);
        
        if (left <= right && right < nums.size() && nums[left] == target) {
            if (nums[right] == target) return right - left + 1;
            else return right - left;
        }

        return 0;
    }


    int lowwer_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;

        while (left < right) {
            int mid = left + (right-left)/2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    };


    int upper_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;

        while (left < right) {
            int mid = left + (right-left)/2;
            if(nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    };

};

33. 搜索旋转排序数组

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

74. 搜索二维矩阵