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.
1var search = function(nums, target) {
2 if (nums.length === 0) return -1;
3 const pivot = findPivot(nums);
4 if (nums[pivot] <= target && target <= nums[nums.length - 1]) {
5 return binarySearch(nums, pivot, nums.length - 1, target);
6 } else {
7 return binarySearch(nums, 0, pivot - 1, target);
8 }
9};
10
11function findPivot(nums) {
12 let left = 0, right = nums.length - 1;
13 while (left < right) {
14 const mid = Math.floor((left + right) / 2);
15 if (nums[mid] > nums[right]) {
16 left = mid + 1;
17 } else {
18 right = mid;
19 }
20 }
21 return left;
22}
23
24function binarySearch(nums, left, right, target) {
25 while (left <= right) {
26 const mid = Math.floor((left + right) / 2);
27 if (nums[mid] === target) return mid;
28 else if (nums[mid] < target) left = mid + 1;
29 else right = mid - 1;
30 }
31 return -1;
32}
33By illuminating the pivot-discernment segmentary, this JavaScript construct lays the groundwork for independently-concerted binary searches adjusted around such discovery, focusing upon array portions with rotated offsets regarded.