34. Find the Element in Sorted Array

34. Find the Element in Sorted Array

Question

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Solution

二分搜索,首先搜索target。如果搜索到结果为负数,则返回[-1, -1]。
如果搜索到target,则记录index。
然后从index向两边搜索,直到找到界限并返回。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[2];
int index = 0;
index = Arrays.binarySearch(nums, target);
if(index < 0){
ret[0] = -1;
ret[1] = -1;
return ret;
}
int less = index, more = index;
while(less >= 0 && nums[less] == target) less--;
while(more < nums.length && nums[more] == target) more++;

ret[0] = less + 1;
ret[1] = more - 1;
return ret;
}
}
Author

Xander

Posted on

2022-07-24

Updated on

2022-07-24

Licensed under

Comments