publicintsearch(int[] nums, int target){ int n = nums.length; // Find the pivot int idx = 0; for (int i = 0; i < n - 1; ++i) { // O(N) if (nums[i] > nums[i + 1]) { idx = i + 1; break; } } // Binary search int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int realMid = (mid + idx) % n; // no duplicate if (nums[realMid] == target) return realMid; if (nums[realMid] > target) { hi = mid - 1; } else { lo = mid + 1; } } return -1; }

Time: $O(N)$ Space: $O(1)$

Two Binary Searches

Use two binary searches. The first one is for finding the pivot.

The searching condition is nums[mid] <= nums[n - 1], which means we want to find the leftmost element that is less than the last element (the real first element).

// [4, 5, 6, 7, 0, 1, 2] publicintsearch(int[] nums, int target){ int n = nums.length;

// search the index (the leftmost index that is less than the last element) int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] <= nums[n - 1]) { hi = mid - 1; } else { lo = mid + 1; } } int idx = lo; // search the target lo = 0; hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int realMid = (mid + idx) % n; if (nums[realMid] == target) return realMid; if (nums[realMid] > target) { hi = mid - 1; } else { lo = mid + 1; } } return -1; }

Time: $O(\log{N})$ Space: $O(1)$

Problem II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

int n = nums.length; int lo = 0, hi = n - 1; // pre-processing while (lo <= hi && nums[lo] == nums[hi]) { lo += 1; // moving lo to a proper place } // could be omitted. idx == lo == n ==> (mid + idx) % n == mid % n == mid if (lo >= n) return nums[0] == target; // test cases: [1] or [1, 1]

// search the index while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] <= nums[n - 1]) { hi = mid - 1; } else { lo = mid + 1; } } int idx = lo;

// search the target lo = 0; hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int realMid = (mid + idx) % n; if (nums[realMid] == target) returntrue; if (nums[realMid] > target) { hi = mid - 1; } else { lo = mid + 1; } } returnfalse; }

Time: $O(\log{N})$

$O(N)$ in the worst case (pre-processing).

Space: $O(1)$

Do it in one loop:

I don’t like this version. Not clear.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

publicbooleansearch(int[] nums, int target){ int n = nums.length; int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) returntrue; if (nums[mid] == nums[lo]) { lo += 1; // found duplicate } elseif (nums[mid] > nums[lo]) { if (nums[mid] > target && nums[lo] <= target) hi = mid - 1; else lo = mid + 1; } else { if (nums[mid] < target && nums[hi] >= target) lo = mid + 1; else hi = mid - 1; } } returnfalse; }

Comment

Junhao Wang

Hi, I was a master student at USC studying Computer Science.