Problem Statement:
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].
Approach:
- 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] and ans[1].
Time & Space Complexity:
Time Complexity: O(logn)
Space Complexity: O(1)
Dry Run
Input: arr = [5, 7, 7, 8, 8, 10], target = 8
Initial: l = 0, r = 5 ans = [-1, -1] --- First While Loop (find first index) --- Loop 1: m = 0 + Math.floor((5 - 0) / 2) = 2 arr[m] = 7 < 8 → true l = m + 1 = 3 Loop 2: m = 3 + Math.floor((5 - 3) / 2) = 4 arr[m] = 8 < 8 → false r = m = 4 Loop 3: m = 3 + Math.floor((4 - 3) / 2) = 3 arr[m] = 8 < 8 → false r = m = 3 Exit (l = 3, r = 3) arr[l] = 8 → ans[0] = 3 --- Second While Loop (find last index) --- Reset: l = 0, r = 5 Loop 1: m = 0 + Math.ceil((5 - 0) / 2) = 3 arr[m] = 8 > 8 → false l = m = 3 Loop 2: m = 3 + Math.ceil((5 - 3) / 2) = 4 arr[m] = 8 > 8 → false l = m = 4 Loop 3: m = 4 + Math.ceil((5 - 4) / 2) = 5 arr[m] = 10 > 8 → true r = m - 1 = 4 Exit (l = 4, r = 4) arr[l] = 8 → ans[1] = 4 --- Final Result --- ans = [3, 4]
Output: Result: [3, 4]
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;
};
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;
}
}
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;
}
}
