剑指offer53-Ⅰ 在排序数组中查找数字Ⅰ【二分查找】

剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述

统计一个数字在排序数组中出现的次数。

示例 1:

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

示例 2:

1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制:

1
0 <= 数组长度 <= 50000

解题思路

方法一:二分查找

先二分查找到target后,在对查找到的数字前后搜索,统计完所有target值的数量

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int search(int[] nums, int target) {
int right = nums.length - 1, left = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
int res = 1;
int temp = mid - 1;
mid++;
while (mid < nums.length && nums[mid] == target) {
res++;
mid++;
}
while (temp >= 0 && nums[temp] == target) {
res++;
temp--;
}
return res;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return 0;
}
}

复杂度分析

时间复杂度:O(log n)

空间复杂度:O(1)

资料

剑指offer53-Ⅰ 在排序数组中查找数字Ⅰ【二分查找】

http://example.com/2021/05/30/剑指offer53-Ⅰ-在排序数组中查找数字Ⅰ/

Author

John Doe

Posted on

2021-05-30

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.