1. 题目描述
统计一个数字在排序数组中出现的次数。
2. 题目分析
题主一开始的方法：看见有序，使用二分，查找到target，向前向后分别遍历到不等于target的数字，因为数组中的target出现的次数是不确定的，所以，可能查找到n次，相当于O(n);面试中，这种写法会被paas掉，所以我们需要用二分查找找到第一次出现target的下标，最后一次出现target的下标，对于target出现的第一次下标,采用以下方式 当mid == 0的时候，也就是证明当前的数是从下标0开始的，则直接返回0(mid) 为了防止数组的越界，我们需要使当前的mid>0且array[mid-1]!=key 对于：right = mid - 1;我们可以理解成当前的key是位于中间的那一个，所以我们需要减少范围，也就是缩小right的值，让mid向前遍历。
if (array
[mid
] == key
) {
if ((mid
== 0) || (mid
> 0 && array
[mid
- 1] != key
)) {
return mid
;
} else {
right
= mid
- 1;
}
}
对于target出现的最后一次下标，采取以下方式 当mid == array.lenth - 1的时候，也就是证明当前的数一直到最后。则直接返回mid 为了防止数组的越界，我们需要使当前的mid<array.lenth - 1且array[mid+1]!=key 对于：i = mid + 1;我们可以理解成当前的key是位于中间的那一个，所以我们需要减少范围，也就是扩大left的值，让mid向后遍历。
if (array
[mid
] == key
) {
if (mid
== array
.length
- 1 || mid
< array
.length
- 1 && array
[mid
+ 1] != key
) {
return mid
;
} else {
left
= mid
+ 1;
}
}
最后，我们返回（第二次出现的下标 - 第一次出现的下标 + 1）
3. 题目代码
class Solution {
public int search(int[] nums
, int target
) {
int num1
= erfenFirst(nums
, 0, nums
.length
- 1, target
);
int num2
= erfenSecond(nums
, 0, nums
.length
- 1, target
);
return num2
- num1
+ 1;
}
public static int erfenFirst(int[] array
, int left
, int right
, int key
) {
int mid
= 0;
while (left
<= right
) {
mid
= (left
+ right
) / 2;
if (array
[mid
] == key
) {
if ((mid
== 0) || (mid
> 0 && array
[mid
- 1] != key
)) {
return mid
;
} else {
right
= mid
- 1;
}
} else if (array
[mid
] > key
) {
right
= mid
- 1;
} else {
left
= mid
+ 1;
}
}
return 1;
}
public static int erfenSecond(int[] array
, int left
, int right
, int key
) {
int i
= left
;
int j
= right
;
while (i
<= j
) {
int mid
= (i
+ j
) / 2;
if (array
[mid
] == key
) {
if (mid
== array
.length
- 1 || mid
< array
.length
- 1 && array
[mid
+ 1] != key
) {
System
.out
.println(mid
);
return mid
;
} else {
i
= mid
+ 1;
}
} else if (array
[mid
] > key
) {
j
= mid
- 1;
} else {
i
= mid
+ 1;
}
}
return 0;
}
}
