35. Search Insert Position
Tags:
Easy
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í của một số target trong một mảng đã được sắp xếp tăng dần. Nếu target có trong mảng, return về chỉ số của nó. Nếu không, return về chỉ số mà target nên được chèn vào để giữ mảng vẫn tăng dần.
TC yêu cầu là O(logn), do đó giải pháp binary search là tối ưu
Approach
left, right lần lượt và 0 và độ dài mảngleft < right mid = Math.floor((left + right)/2) right = mid )left = mid + 1 )left chính là vị trí cần return về (vị trí tìm thấy hoặc vị trí cần chèn)right = mid mà không phải right = mid + 1 ?Mục tiêu của bài toán
nums[i] >= target (tức là vị trí mà target nên xuất hiện nếu chèn vào mảng)Phân tích hai cách cập nhật right
Cách 1: right = mid
right = mid Cách 2: right = mid + 1
left < right mà không phải left <= right ?Điều kiện dừng left < right (thay vì left <= right) trong bài toán "Search Insert Position" và các bài toán tìm vị trí chèn (lower bound) là để đảm bảo khi vòng lặp kết thúc, biến left sẽ trỏ đúng vào vị trí cần return về, không bị lặp vô hạn và không cần kiểm tra lại phần tử cuối cùng
Giải thích chi tiết
nums[left] >= target hoặc vị trí chèn)left = right + 1 ), như vậy cần phải kiểm tra lại phần tử cuối cùng ngoài vòng lặp hoặc xử lý đặc biệt, dễ gây lỗiTổng kết
Solution
1function searchInsert(nums: number[], target: number): number {
2 let left = 0, right = nums.length;
3 while (left < right) {
4 const mid = left + Math.floor((right - left) / 2);
5 if (nums[mid] >= target) right = mid
6 else left = mid + 1
7 }
8 return left;
9};