每日简短一刷，保持手感系列
题目：统计一个数字在排序数组中出现的次数。
示例 1:

输入: nums = [5,7,7,8,8,10], target = 8

输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6

输出: 0
提示：

0 <= nums.length <= 105

-109 <= nums[i] <= 109

nums 是一个非递减数组
-109 <= target <= 109
就单单看题目，这道理逻辑非常直白和简单，查到一个数字在排序数组中出现的次数，直接遍历一次统计就完了
classSolution
{

publicintsearch(int[] nums, int target)
{

int
 cnt = 
0
;

for
 (
int
 i = 
0
; i < nums.length; i++) {

if
 (nums[i] == target) cnt++;

        }

return
 cnt;

    }

}

时间复杂度 O(n)，空间复杂度 O(1)
但是这不免也太简单了吧？
所以要注意提示，nums 是一个非递减数组，从这个提示可以得知它是一个有序数组，看到有序二字就该有应激反应：二分法。
不过这不是朴素二分，而是二分的变型。
按照题意我们应该利用二分找到和 target 相等的数组最左位置，然后之后有两个选择
  1. 根据这个最左位置直接往后遍历
  2. 再通过二分找到和 target 相等的数组最右位置
如果你选择第一种，其实时间复杂度还是变成了 O(n)。
所以我们选择第二种，继续利用变型的二分找到最后的位置，最终最右的位置减去最左的位置再+1得到的值就是重复的次数。
让我们看一下代码：

classSolution
{

publicintsearch(int[] nums, int target)
{

int
 len = nums.length;

if
 (len == 
0
) { 
//空数组直接返回，不然下面 nums[left] 就抛错了。
return0
;

        }

int
 left = 
0
, right = len-
1
;

//先二分找到最左节点
while
(left < right) {

int
 mid = left + right >> 
1
;

if
 (nums[mid] >= target) {

            right = mid;

          } 
else
 {

            left = mid + 
1
;

          } 

        }


// 说明没找到，直接返回 0 
if
 (nums[left] != target) {

return0
;

        }


int
 rightLeft = left;

        right = len - 
1
;

//二分找到最右节点
while
 (left < right) {

int
 mid = left + right + 
1
 >> 
1
; 
//二分边界处理，不然会死循环
if
 (nums[mid] <= target) {

            left = mid;

          } 
else
 {

            right = mid - 
1
;

          }

        }


return
 right - rightLeft + 
1
;


    }

}

相信思路还是挺简单的，但是十个二分九个错，所以二分的细节还是需要特意去画画的，不然容易出错，之后我再专门写一篇分析分析二分的变型。
一道简单题，可点击原文进行练习。
继续阅读
阅读原文
关键词
数组
算法
nums.length
数字
位置