-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSearchRotSortArr.java
More file actions
100 lines (77 loc) · 3.12 KB
/
SearchRotSortArr.java
File metadata and controls
100 lines (77 loc) · 3.12 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.util.*;
class SearchRotSortArr {
public static int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// {4,5,6,7,0,1,2}; t = 3
// nums[left] = 4; nums[right] = 2; nums[mid] = 7
while(left <= right) {
int mid = (right + left) / 2;
// Check if mid elem is the target
if (nums[mid] == target) {
return mid;
}
// Determine which half is sorted
if (nums[left] <= nums[mid]) {
// left half is sorted
if (nums[left] <= target && target < nums[mid]) {
// 4 <= 3 && 3 < 7? No
// Target is in the left half
right = mid - 1;
} else { // 4 <= 3 && 3 < 7 => {7,0,1,2}
// target is in right half
// nums[left] = 0
left = mid + 1;
}
} else {
// Right is sorted
if (nums[mid] < target && target <= nums[right]) {
// Target is in the right half
left = mid + 1;
} else {
// Target is in the left half
right = mid - 1;
}
}
}
// Target not found
return -1;
}
public static void main(String[] args) {
int[] nums1 = {4,5,6,7,0,1,2};
int target1 = 0; // 4
int[] nums2 = {4,5,6,7,0,1,2};
int target2 = 3; // -1
System.out.println(search(nums1, target1));
System.out.println(search(nums2, target2));
}
}
/*
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
[4,5,6,7,0,1,2]; target = 0
Targ < 7; could be on either side of 7
Look at right; targ < 4, so search to right of mid
new left is mid + 1, nums[4] = 0 => [0,1,2]
nums[mid] = 1; targ < 1;; check to left, which is = targ
1. Binary Search with Condition Checks
Two pointers, left and right, for start and end of search range
Calc middle index, mid
2. ID sorted halves
Since the array is rotated, either the left half or the right half of the array,
relative to mid, will be sorted
If nums[left] <= nums[mid]: left half, from left to mid, is sorted
If nums[mid] <= nums[right]: right half, from mid to right, is sorted
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
*/