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.
1var search = function(nums, target) {
2 let left = 0, right = nums.length - 1;
3 while (left <= right) {
4 const mid = Math.floor((left + right) / 2);
5 if (nums[mid] === target) return mid;
6 if (nums[left] <= nums[mid]) {
7 if (nums[left] <= target && target < nums[mid]) {
8 right = mid - 1;
9 } else {
10 left = mid + 1;
11 }
12 } else {
13 if (nums[mid] < target && target <= nums[right]) {
14 left = mid + 1;
15 } else {
16 right = mid - 1;
17 }
18 }
19 }
20 return -1;
21};
22This JavaScript function adapts binary search, interpreting a rotated array segment-wise. It pinpoints if a portion is sorted, isolates potential target placement, and toggles direction accordant to insights, ensuring efficient target retrieval.
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.