34. Find First and Last Position of Element in Sorted Array
Tags:
Medium
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm vị trí bắt đầu và kết thúc của một giá trị target trong một mảng số nguyên đã được sắp xếp không giảm
Nếu không tìm thấy thì return [-1, -1]
Yêu cầu thuật toán có TC O(logn), tức là phải dùng binary search thay vì duyệt tuyến tính
Approach
target target target return về [-1, -1] Solution
1function searchRange(nums: number[], target: number): number[] {
2 function leftSearch(nums: number[], target: number): number {
3 let left = 0, right = nums.length - 1
4 let res = -1
5 while (left <= right) {
6 const mid = left + Math.floor((right - left) / 2)
7 if (nums[mid] < target) left = mid + 1
8 else {
9 if (nums[mid] === target) res = mid;
10 right = mid - 1
11 }
12 }
13
14 return res
15 }
16
17 function rightSearch(nums: number[], target: number): number {
18 let left = 0, right = nums.length - 1
19 let res = -1
20 while (left <= right) {
21 const mid = left + Math.floor((right - left) / 2)
22 if (nums[mid] > target) right = mid - 1
23 else {
24 if (nums[mid] === target) res = mid;
25 left = mid + 1
26 }
27 }
28
29 return res
30 }
31
32 const first = leftSearch(nums, target)
33 if (first === -1) return [-1, -1]
34 const last = rightSearch(nums, target)
35 return [first, last]
36};