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 { public int[] searchRange(int[] nums, int target) { int[] ans = {-1, -1}; int n = nums.length; if (n == 0) return ans; int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } if (nums[r] != target) return ans; ans[0] = r; l = 0; r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] <= target) l = mid; else r = mid - 1; } ans[1] = r; return ans; } }

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

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

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