This problem asks us to find the first and last positions of a given target in a sorted array. If the target is not found, return [-1, -1].
Steps
- Use binary search twice:
- Once to find the **first occurrence** (left bound)
- Once to find the **last occurrence** (right bound)
- Store results in
ans[0]andans[1].
Dry Run
Input: [5,7,7,8,8,10], target = 8
- First binary search finds index
3 - Second binary search finds index
4 - Answer:
[3, 4]
Input: [5,7,7,8,8,10], target = 6
Output: [-1, -1]
Input: [5,7,7,8,8,10], target = 0
Output: [-1, -1]
Time & Space Complexity
- Time Complexity: O(log n)
- Space Complexity: 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) l = m + 1;
else r = m;
}
if (arr[l] === target) ans[0] = l;
l = 0;
r = arr.length - 1;
while (l < r) {
let m = l + Math.ceil((r - l) / 2);
if (arr[m] > target) r = m - 1;
else l = m;
}
if (arr[l] === target) ans[1] = l;
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) l = m + 1;
else r = m;
}
if (arr[l] == target) ans[0] = l;
l = 0; r = arr.size() - 1;
while (l < r) {
int m = l + (r - l + 1) / 2;
if (arr[m] > target) r = m - 1;
else l = m;
}
if (arr[l] == target) ans[1] = l;
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) l = m + 1;
else r = m;
}
if (arr[l] == target) ans[0] = l;
l = 0; r = arrSize - 1;
while (l < r) {
int m = l + (r - l + 1) / 2;
if (arr[m] > target) r = m - 1;
else l = m;
}
if (arr[l] == target) ans[1] = l;
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) l = m + 1;
else r = m;
}
if (arr[l] == target) ans[0] = l;
l = 0; r = arr.length - 1;
while (l < r) {
int m = l + (r - l + 1) / 2;
if (arr[m] > target) r = m - 1;
else l = m;
}
if (arr[l] == target) ans[1] = l;
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:
l = m + 1
else:
r = m
if l < len(arr) and arr[l] == target:
ans[0] = l
l, r = 0, len(arr) - 1
while l < r:
m = l + (r - l + 1) // 2
if arr[m] > target:
r = m - 1
else:
l = m
if l < len(arr) and arr[l] == target:
ans[1] = l
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) l = m + 1;
else r = m;
}
if (arr[l] == target) ans[0] = l;
l = 0; r = arr.Length - 1;
while (l < r) {
int m = l + (r - l + 1) / 2;
if (arr[m] > target) r = m - 1;
else l = m;
}
if (arr[l] == target) ans[1] = l;
return ans;
}
}
