publicintsearch(int[] nums, int target) { intn= nums.length; // Find the pivot intidx=0; for (inti=0; i < n - 1; ++i) { // O(N) if (nums[i] > nums[i + 1]) { idx = i + 1; break; } } // Binary search intlo=0, hi = n - 1; while (lo <= hi) { intmid= lo + (hi - lo) / 2; intrealMid= (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).

// search the index (the leftmost index that is less than the last element) intlo=0, hi = n - 1; while (lo <= hi) { intmid= lo + (hi - lo) / 2; if (nums[mid] <= nums[n - 1]) { hi = mid - 1; } else { lo = mid + 1; } } intidx= lo; // search the target lo = 0; hi = n - 1; while (lo <= hi) { intmid= lo + (hi - lo) / 2; intrealMid= (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.

intn= nums.length; intlo=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) { intmid= lo + (hi - lo) / 2; if (nums[mid] <= nums[n - 1]) { hi = mid - 1; } else { lo = mid + 1; } } intidx= lo;

// search the target lo = 0; hi = n - 1; while (lo <= hi) { intmid= lo + (hi - lo) / 2; intrealMid= (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) { intn= nums.length; intlo=0, hi = n - 1; while (lo <= hi) { intmid= 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; }