题目

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

考察知识点

双指针、二分查找

方法一、暴力拆解

说起来挺惭愧的，因为刷算法题刷的少，我一看这道题就一个for循环搞定了，一看解析才知道我是沙比，这道题主要考察二分查找，但是我还是把我的解法写出来吧。

思路

暴力循环然后累加，如果大于target则代表后面再没有了。

代码

  1.         // 最简单的方法，暴力循环
  2.     public static int search(int[] nums, int target) {
  3.         int result = 0;
  4.         for (int i = 0; i < nums.length; i++) {
  5.             if (nums[i] == target) {
  6.                 result++;
  7.                 // 如果大于了，说明后面再没有了
  8.             } else if (nums[i] > target) {
  9.                 return result;
  10.             }
  11.         }
  12.         return result;
  13.     }

复杂度分析

时间复杂度：O(n) 没有利用到升序排列的条件。
空间复杂度：O(1)

方法二、二分查找

思路

用两次二分查找，找出左右边界，在用右边界-左边界-1就是最后需要的结果。
Offer53-1|在排序数组中查找数字 I - 图1

代码

思想懂了，代码没懂= =!!!

    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }

    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }

复杂度分析

时间复杂度：O(logn) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(logn)，一共会执行两次，因此总时间复杂度为 O(logn)。
空间复杂度：O(1)