The essence of this approach is to perform a binary search with a twist, considering the rotation. We first determine which part of the array is sorted: the left or the right. This allows us to intelligently decide where to perform the binary search. If the target lies within the sorted side, we adjust the search range accordingly. Otherwise, we continue the search on the unsorted side, which in the next iteration becomes a new array.
Time Complexity: O(log n) because each step reduces the search space by half.
Space Complexity: O(1) as no extra space is used aside from variables.
1#include <stdio.h>
2int search(int* nums, int numsSize, int target) {
3 int left = 0, right = numsSize - 1;
4 while (left <= right) {
5 int mid = left + (right - left) / 2;
6 if (nums[mid] == target) return mid;
7 if (nums[left] <= nums[mid]) {
8 if (nums[left] <= target && target < nums[mid]) {
9 right = mid - 1;
10 } else {
11 left = mid + 1;
12 }
13 } else {
14 if (nums[mid] < target && target <= nums[right]) {
15 left = mid + 1;
16 } else {
17 right = mid - 1;
18 }
19 }
20 }
21 return -1;
22}
23This approach employs a standard binary search. The array is divided based on whether the left or the right half is sorted. If the left part is sorted, we check whether the target falls within that sorted range. If it does, the right boundary is adjusted; otherwise, the search continues in the right half, adjusting the left boundary, and vice versa for the right sorted half.
This decomposition-based approach first identifies the pivot index where rotation occurs. Once the break index is acquired, the target search bifurcates: running binary search on subarrays from the determined split point to either the beginning or end of the array.
Time Complexity: O(log n) to find the pivot and additional O(log n) for binary search, leading to O(log n) overall.
Space Complexity: O(1) due to in-place operations.
1class Solution {
2 public int search(int[] nums, int target) {
3 if (nums.length == 0) return -1;
4 int pivot = findPivot(nums);
5 if (nums[pivot] <= target && target <= nums[nums.length - 1])
6 return binarySearch(nums, pivot, nums.length - 1, target);
7 else
8 return binarySearch(nums, 0, pivot - 1, target);
9 }
10
11 private int findPivot(int[] nums) {
12 int left = 0, right = nums.length - 1;
13 while (left < right) {
14 int mid = left + (right - left) / 2;
15 if (nums[mid] > nums[right])
16 left = mid + 1;
17 else
18 right = mid;
19 }
20 return left;
21 }
22
23 private int binarySearch(int[] nums, int left, int right, int target) {
24 while (left <= right) {
25 int mid = left + (right - left) / 2;
26 if (nums[mid] == target) return mid;
27 else if (nums[mid] < target) left = mid + 1;
28 else right = mid - 1;
29 }
30 return -1;
31 }
32}
33This approach discriminates between pre- and post-pivot segments, employing typical binary search methodically after systematically determining rotational indices, creating a dual-binary search operation.