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.
1#include <stdio.h>
2int findPivot(int* nums, int numsSize) {
3 int left = 0, right = numsSize - 1;
4 while (left < right) {
5 int mid = left + (right - left) / 2;
6 if (nums[mid] > nums[right])
7 left = mid + 1;
8 else
9 right = mid;
10 }
11 return left;
12}
13
14int binarySearch(int* nums, int left, int right, int target) {
15 while (left <= right) {
16 int mid = left + (right - left) / 2;
17 if (nums[mid] == target) return mid;
18 else if (nums[mid] < target) left = mid + 1;
19 else right = mid - 1;
20 }
21 return -1;
22}
23
24int search(int* nums, int numsSize, int target) {
25 if (numsSize == 0) return -1;
26 int pivot = findPivot(nums, numsSize);
27 if (nums[pivot] <= target && target <= nums[numsSize - 1])
28 return binarySearch(nums, pivot, numsSize - 1, target);
29 else
30 return binarySearch(nums, 0, pivot - 1, target);
31}
32This solution breaks the problem down by finding a rotation pivot index. The strategy shifts to standard binary search, applied twice on sub-sections of the array pre-determined by the pivot, thus achieving efficiency.