‘Search in Rotated Sorted Array’ in LeetCode (Medium)
📌 Problem
https://leetcode.com/problems/search-in-rotated-sorted-array/
📌 Answer
The point
- set judgement to check two points
- whether which part is ordered
- whether target is in that range
- and move
- there is an constraint
You must write an algorithm with O(log n) runtime complexity.
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
28
29
30
31
32
33
34
35
36
37
class Solution {
public int search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
int mid;
while (start <= end){
mid = (start + end) / 2;
if (nums[mid] == target) return mid;
// 1. check whether which part is ordered
if (nums[start] <= nums[mid]) {
// 2. check whether target is in that range
if (target < nums[mid] && target >= nums[start])
end = mid - 1;
else
start = mid + 1;
}
// 1. check whether which part is ordered
if (nums[mid] <= nums[end]) {
// 2. check whether target is in that range
if (target > nums[mid] && target <= nums[end])
start = mid + 1;
else
end = mid - 1;
}
}
return -1;
}
}
The source : https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14472/Java-AC-Solution-using-once-binary-search
Comments powered by Disqus.