LeetCode 34: Binary Search Range

LeetCode 34: Binary Search Range

Given an array of integers sorted in ascending order, find the starting and ending positions of a given target value. If the target is not found, return [-1, -1].

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]

Constraints: - The array is non-decreasing.

Advanced: Design an algorithm with O(log n) time complexity.

Solution Approaches:

Binary Search: To find the first occurrence, use binary search with condition nums[mid] >= target to find the leftmost index. For the last occurrence, use nums[mid] <= target to find the rightmost index.

Code Examples:

Java:

class Solution {<br/>    public int[] searchRange(int[] nums, int target) {<br/>        int[] ans = {-1, -1};<br/>        int n = nums.length;<br/>        if (n == 0) return ans;<br/>        int l = 0, r = n - 1;<br/>        while (l < r) {<br/>            int mid = l + r >> 1;<br/>            if (nums[mid] >= target) r = mid;<br/>            else l = mid + 1;<br/>        }<br/>        if (nums[r] != target) return ans;<br/>        ans[0] = r;<br/>        l = 0; r = n - 1;<br/>        while (l < r) {<br/>            int mid = l + r + 1 >> 1;<br/>            if (nums[mid] <= target) l = mid;<br/>            else r = mid - 1;<br/>        }<br/>        ans[1] = r;<br/>        return ans;<br/>    }<br/>}

C++:

class Solution {<br/>public:<br/>    vector<int> searchRange(vector<int>& nums, int target) {<br/>        vector<int> ans = {-1, -1};<br/>        int n = nums.size();<br/>        if (n == 0) return ans;<br/>        int l = 0, r = n - 1;<br/>        while (l < r) {<br/>            int mid = l + r >> 1;<br/>            if (nums[mid] >= target) r = mid;<br/>            else l = mid + 1;<br/>        }<br/>        if (nums[r] != target) return ans;<br/>        ans[0] = r;<br/>        l = 0; r = n - 1;<br/>        while (l < r) {<br/>            int mid = l + r + 1 >> 1;<br/>            if (nums[mid] <= target) l = mid;<br/>            else r = mid - 1;<br/>        }<br/>        ans[1] = r;<br/>        return ans;<br/>    }<br/>};

Python:

class Solution:<br/>    def searchRange(self, nums: List[int], target: int) -> List[int]:<br/>        ans = [-1, -1]<br/>        n = len(nums)<br/>        if n == 0: return ans<br/>        l, r = 0, n - 1<br/>        while l < r:<br/>            mid = l + r >> 1<br/>            if nums[mid] >= target: r = mid<br/>            else: l = mid + 1<br/>        if nums[r] != target: return ans<br/>        ans[0] = r<br/>        l, r = 0, n - 1<br/>        while l < r:<br/>            mid = l + r + 1 >> 1<br/>            if nums[mid] <= target: l = mid<br/>            else: r = mid - 1<br/>        ans[1] = r<br/>        return ans<br/>

Tags: LeetCode, Binary Search, Algorithm, Coding Interview, Problem Solving, Python, Java, C++