This version improves clarity by separating the two binary searches more cleanly. We use one binary search to find the first index, and another to find the last index of the target.
Steps
- Binary search for the **first index** (on match, shift right side)
- Binary search for the **last index** (on match, shift left side)
- Update
ans[0]andans[1]accordingly
Dry Run
Input: [5,7,7,8,8,10], target = 8
- First binary search finds first index
3 - Second binary search finds last index
4 - Output:
[3, 4]
Input: target = 6 → Output: [-1, -1]
Input: target = 0 → Output: [-1, -1]
Time & Space Complexity
- Time: O(log n)
- Space: O(1)
var searchRange = function(arr, target) {
let l = 0;
let r = arr.length - 1;
let ans = [-1, -1];
while (l <= r) {
let m = l + Math.floor((r - l) / 2);
if (arr[m] === target) {
ans[0] = m;
r = m - 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
l = 0;
r = arr.length - 1;
while (l <= r) {
let m = l + Math.floor((r - l) / 2);
if (arr[m] === target) {
ans[1] = m;
l = m + 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
};
vector searchRange(vector& arr, int target) {
int l = 0, r = arr.size() - 1;
vector ans = {-1, -1};
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[0] = m;
r = m - 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
l = 0; r = arr.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[1] = m;
l = m + 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
int* searchRange(int* arr, int arrSize, int target, int* returnSize) {
int* ans = (int*)malloc(2 * sizeof(int));
*returnSize = 2;
ans[0] = ans[1] = -1;
int l = 0, r = arrSize - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[0] = m;
r = m - 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
l = 0; r = arrSize - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[1] = m;
l = m + 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
public class Solution {
public int[] searchRange(int[] arr, int target) {
int[] ans = {-1, -1};
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[0] = m;
r = m - 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
l = 0; r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[1] = m;
l = m + 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
}
def searchRange(arr, target):
ans = [-1, -1]
l, r = 0, len(arr) - 1
while l <= r:
m = l + (r - l) // 2
if arr[m] == target:
ans[0] = m
r = m - 1
elif arr[m] < target:
l = m + 1
else:
r = m - 1
l, r = 0, len(arr) - 1
while l <= r:
m = l + (r - l) // 2
if arr[m] == target:
ans[1] = m
l = m + 1
elif arr[m] < target:
l = m + 1
else:
r = m - 1
return ans
public class Solution {
public int[] SearchRange(int[] arr, int target) {
int[] ans = {-1, -1};
int l = 0, r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[0] = m;
r = m - 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
l = 0; r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == target) {
ans[1] = m;
l = m + 1;
} else if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
}
