剑指Offer系列（java版，详细解析）53.在排序数组中查找数字
题目描述
剑指 Offer 53 - I. 在排序数组中查找数字 I
难度简单119收藏分享切换为英文接收动态反馈
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
限制：
0 <= 数组长度 <= 50000
**注意：**本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
测试用例
- 功能测试（数组中包含要查找的数字；数组中没有要查找的数字；要查找的数字在数组中出现一次/多次）
- 边界值测试(查找数组中的最大值、最小值；数组中只有一个数字)
- 特殊输入测试（表示数组的指针为空指针）
题目考点
- 考察应聘者的只是迁移能力。
- 考察应聘者对二分查找算法的理解程度。
解题思路
一看到在排序数组中查找，大家一定能想到二分查找法，但是怎么用可以减少复杂度，that is problem.
- 利用二分查找法找出最早(左)出现的k的下标
- 利用二分查找法找出最晚(右)出现的k的下标
class Solution {
public int search(int[] nums, int target) {
// 搜索右边界 right
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] <= target) i = m + 1;
else j = m - 1;
}
int right = i;
// 若数组中无 target ，则提前返回
if(j >= 0 && nums[j] != target) return 0;
// 搜索左边界 right
i = 0; j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] < target) i = m + 1;
else j = m - 1;
}
int left = j;
return right - left - 1;
}
}