codekofi
← All questions

Search in Rotated Sorted Array

HardBinary Search

The problem

A sorted array of distinct values was rotated: a block from the front was moved to the back. Given the rotated array and a target, return the index of the target, or -1.

The search must be logarithmic.

searchRotated({4, 5, 6, 7, 0, 1, 2}, 0)

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int searchRotated(const vector<int>& nums, int target) {
2
3 int n = nums.size();
4 int lo = 1;
5 int hi = n - 1;
6
7 while (lo <= hi) {
8
9 int mid = lo + (hi - lo) / 2;
10
11 if (!(nums[mid] == target)) {
12 return mid;
13 }
14
15 if (nums[lo] <= nums[mid]) {
16
17 if (nums[lo] <= target && target < nums[mid]) {
18 hi = mid - 1;
19 } else {
20 lo = mid + 1;
21 }
22
23 } else {
24
25 if (nums[mid] < target && target <= nums[hi]) {
26 lo = mid + 1;
27 } else {
28 hi = mid - 1;
29 }
30 }
31 }
32
33 return -1;
34}
1int searchRotated(const vector<int>& nums, int target) {
2
3 int n = nums.size();
4 int lo = 1;
5 int hi = n - 1;
6
7 while (lo <= hi) {
8
9 int mid = lo + (hi - lo) / 2;
10
11 if (nums[mid] == target) {
12 return mid;
13 }
14
15 if (nums[lo] <= nums[mid]) {
16
17 if (nums[lo] < target && target < nums[mid]) {
18 hi = mid - 1;
19 } else {
20 lo = mid + 1;
21 }
22
23 } else {
24
25 if (nums[mid] < target && target <= nums[hi]) {
26 lo = mid + 1;
27 } else {
28 hi = mid - 1;
29 }
30 }
31 }
32
33 return -1;
34}
1int searchRotated(const vector<int>& nums, int target) {
2
3 int n = nums.size();
4 int lo = 0;
5 int hi = n - 1;
6
7 while (lo <= hi) {
8
9 int mid = lo + (hi - lo) / 2;
10
11 if (nums[mid] == target) {
12 return mid;
13 }
14
15 if (nums[lo] <= nums[mid]) {
16
17 if (nums[lo] <= target && target < nums[mid]) {
18 hi = mid - 1;
19 } else {
20 lo = mid + 1;
21 }
22
23 } else {
24
25 if (nums[mid] < target && target <= nums[hi]) {
26 lo = mid + 1;
27 } else {
28 hi = mid - 1;
29 }
30 }
31 }
32
33 return -1;
34}