Problem Statement:
This problem requires finding a target value in a rotated sorted array nums. Using a modified binary search, we determine which half of the array is sorted in each iteration and narrow the search range accordingly.
Approach:
- Initialize two pointers:
l = 0andr = nums.length - 1. - While
l ≤ r: - Compute mid:
m = l + floor((r - l) / 2). - If
nums[m] === target, returnm. - Check which side is sorted:
- If
nums[l] ≤ nums[m], left side is sorted: - If
target ∈ [nums[l], nums[m]], moveleft: r = m - 1.
- If
- Else, move right:
l = m + 1. - Else, right side is
sorted: - If target
∈ (nums[m], nums[r]], move right: l = m + 1. - Else, move left:
r = m - 1. - If not found,
return -1.
Time & Space Complexity:
Time Complexity: O(logn)
Space Complexity: O(1)
Dry Run
Input: arr = [4,5,6,7,0,1,2], target = 0
Initial: l = 0, r = 6 arr = [4,5,6,7,0,1,2], target = 0 Loop 1: m = 0 + Math.floor((6 - 0) / 2) = 3 arr[m] = 7 arr[l] <= arr[m] → 4 <= 7 → true (left side sorted) target >= arr[l] && target < arr[m] → 0 >= 4 && 0 < 7 → false Else → l = m + 1 = 4 Loop 2: m = 4 + Math.floor((6 - 4) / 2) = 5 arr[m] = 1 arr[l] <= arr[m] → 0 <= 1 → true (left side sorted) target >= arr[l] && target < arr[m] → 0 >= 0 && 0 < 1 → true r = m - 1 = 4 Loop 3: m = 4 + Math.floor((4 - 4) / 2) = 4 arr[m] = 0 target === arr[m] → 0 === 0 → true → return 4
Output: Result: 4
var search = function(arr, target) {
let l = 0;
let r = arr.length - 1;
while (l <= r) {
let m = l + Math.floor((r - l) / 2);
if (target === arr[m]) {
return m;
}
if (arr[l] <= arr[m]) {
if (target >= arr[l] && target < arr[m]) {
r = m - 1;
} else {
l = m + 1;
}
} else {
if (target > arr[m] && target <= arr[r]) {
l = m + 1;
} else {
r = m - 1;
}
}
}
return -1;
};
def search(arr, target):
l, r = 0, len(arr) - 1
while l <= r:
m = l + (r - l) // 2
if arr[m] == target:
return m
if arr[l] <= arr[m]:
if target >= arr[l] and target < arr[m]:
r = m - 1
else:
l = m + 1
else:
if target > arr[m] and target <= arr[r]:
l = m + 1
else:
r = m - 1
return -1
public class Solution {
public int search(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) return m;
if (arr[l] <= arr[m]) {
if (target >= arr[l] && target < arr[m]) r = m - 1;
else l = m + 1;
} else {
if (target > arr[m] && target <= arr[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}
}
int search(vector& arr, int target) {
int l = 0, r = arr.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) return m;
if (arr[l] <= arr[m]) {
if (target >= arr[l] && target < arr[m]) r = m - 1;
else l = m + 1;
} else {
if (target > arr[m] && target <= arr[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}
int search(int arr[], int size, int target) {
int l = 0, r = size - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) return m;
if (arr[l] <= arr[m]) {
if (target >= arr[l] && target < arr[m]) r = m - 1;
else l = m + 1;
} else {
if (target > arr[m] && target <= arr[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}
public class Solution {
public int Search(int[] arr, int target) {
int l = 0, r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) return m;
if (arr[l] <= arr[m]) {
if (target >= arr[l] && target < arr[m]) r = m - 1;
else l = m + 1;
} else {
if (target > arr[m] && target <= arr[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}
}
