[数据结构与算法]【刷】剑指 Offer 53 - I. 在排序数组中查找数字 I

作者：Geekwyz

在排序数组中查找数字 I

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

• 解题思路：

第一种思路就是暴力，定义一个变量i=0，用于计数，然后遍历数组，如果匹配则另i加1，
时间复杂度为O(n)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int k = 0;
        int len = nums.size() - 1;
        if (nums.size() == 0) return 0;
        for (int i = 0;i <= len;i++) {
            if (target == nums[i]) {
                ++k;
            }
        }
    return k;
    }
};

第二种思路就是二分查找
在面试中出现这题面试官大差不差想考里的就是二分查找了
面试时候一定要想到

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int cout = 0;
        while (left < right) {
            int mid = (right + left) >> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        while (left < nums.size() && nums[left++] == target) cout++;
        return cout;
    }
};