Description:
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Examples:
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]Solution in Python:
To solve this problem efficiently with a runtime complexity of O(log n), we can use a binary search approach. We will implement two separate binary searches: one to find the leftmost (first) occurrence of the target and one to find the rightmost (last) occurrence of the target.
Python
from typing import List
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def findLeft(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
def findRight(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right
left_index = findLeft(nums, target)
right_index = findRight(nums, target)
# Check if the target is not in the array
if left_index <= right_index and right_index < len(nums) and nums[left_index] == target and nums[right_index] == target:
return [left_index, right_index]
else:
return [-1, -1]Detailed Explanation:
- Binary Search for Leftmost Index (
findLeft):- Initialize
leftto 0 andrightto the last index ofnums. - Use a while loop that runs as long as
leftis less than or equal toright. - Calculate
midas the midpoint ofleftandright. - If the element at
midis less than the target, move theleftpointer tomid + 1. - Otherwise, move the
rightpointer tomid - 1. - This search will stop at the smallest index where
nums[index]is greater than or equal to the target.
- Initialize
- Binary Search for Rightmost Index (
findRight):- Initialize
leftto 0 andrightto the last index ofnums. - Use a while loop that runs as long as
leftis less than or equal toright. - Calculate
midas the midpoint ofleftandright. - If the element at
midis less than or equal to the target, move theleftpointer tomid + 1. - Otherwise, move the
rightpointer tomid - 1. - This search will stop at the largest index where
nums[index]is less than or equal to the target.
- Initialize
- Final Check:
- After finding the potential leftmost and rightmost indices, we need to check if the target exists within the range.
- If the
left_indexis less than or equal to theright_index, and both indices are within the bounds of the array, and the elements at these indices are equal to the target, return these indices. - If not, return
[-1, -1]indicating the target is not present in the array.
This approach ensures the solution runs in O(log n) time complexity due to the binary search used for both the leftmost and rightmost indices.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
// Helper function to find the leftmost index of the target
function findLeft(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
// Helper function to find the rightmost index of the target
function findRight(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
// Find the leftmost index of the target
let leftIndex = findLeft(nums, target);
// Find the rightmost index of the target
let rightIndex = findRight(nums, target);
// Check if the target is not in the array
if (leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] === target && nums[rightIndex] === target) {
return [leftIndex, rightIndex];
} else {
return [-1, -1];
}
};Solution in Java:
Java
import java.util.Arrays;
class Solution {
public int[] searchRange(int[] nums, int target) {
// Find the leftmost index of the target
int leftIndex = findLeft(nums, target);
// Find the rightmost index of the target
int rightIndex = findRight(nums, target);
// Check if the target is not in the array
if (leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] == target && nums[rightIndex] == target) {
return new int[]{leftIndex, rightIndex};
} else {
return new int[]{-1, -1};
}
}
// Helper function to find the leftmost index of the target
private int findLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
// Helper function to find the rightmost index of the target
private int findRight(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
// Example usage:
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(Arrays.toString(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8))); // Output: [3, 4]
System.out.println(Arrays.toString(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6))); // Output: [-1, -1]
System.out.println(Arrays.toString(solution.searchRange(new int[]{}, 0))); // Output: [-1, -1]
}
}Solution in C#:
C#
using System;
public class Solution {
public int[] SearchRange(int[] nums, int target) {
// Find the leftmost index of the target
int leftIndex = FindLeft(nums, target);
// Find the rightmost index of the target
int rightIndex = FindRight(nums, target);
// Check if the target is not in the array
if (leftIndex <= rightIndex && rightIndex < nums.Length && nums[leftIndex] == target && nums[rightIndex] == target) {
return new int[] { leftIndex, rightIndex };
} else {
return new int[] { -1, -1 };
}
}
// Helper function to find the leftmost index of the target
private int FindLeft(int[] nums, int target) {
int left = 0, right = nums.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
// Helper function to find the rightmost index of the target
private int FindRight(int[] nums, int target) {
int left = 0, right = nums.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
}