题目描述:
统计一个数字在排序数组中出现的次数。
示例:
Input: nums = [5,7,7,8,8,10], target = 8
Output: 2
Input: nums = [5,7,7,8,8,10], target = 6
Output: 0
解题思路:
本题主要是考察二分法的边界条件的确定问题。题目中隐藏的信息是该数组是已经排序好的,而从示例可以看到,是按升序排序的,因此如果一个数字在该数组中重复出现,那么必定是连续的。想统计数组的出现次数只需要找到这个数字的左右边界,而二分法的一般结束循环的条件为,左指针索引大于右指针索引,因此只需要不断的缩小二分的范围,就可以找到左右边界。
算法代码:
class Solution {
public int search(int[] nums, int target) {
// 首先初始化左右指针。
int left = 0;
int right = nums.length-1;
// 确认target的右边界
while(left <= right){
int mid = (left + right) / 2; // 由于mid每次都要确定,因此写在循环之中,每次都重新定义。
if(nums[mid]<=target) left = mid + 1; // 这里要注意到这个等于号。等于号的意义在于如果找到了这个数,那么我就要将left往右移,直到mid不再等于该数,这时也就刚刚好跳出该数,也就确定了右边界。
else right = mid - 1;
}
int rightIndex = left; // 此时将left作为右边界。
if(right > 0 && nums[right]!=target) return 0; // 如果存在target, 那么当left出target,right则应该刚好跳进该数。如果不相等,则不存在
left = 0; right = nums.length - 1; //再次初始化指针
// 确定
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] < target) left = mid + 1;
else right = mid - 1; // 这时等号在右指针中,当相等时,右指针不断左移,直到找到左边界。
}
int leftIndex = right;
return rightIndex - leftIndex - 1;
}
}
小tips:
二分法的循环条件一般为左指针索引大于右指针索引,因此在循环中,一定要设定相应的条件使得左指针增加或右指针增加,不然就会陷入死循环之中。
但是也有例外,需要视实际情况而定。
如:剑指 Offer 11. 旋转数组的最小数字
如有错误,欢迎大家留言指出,大家一起进步



