Vị Trí Chèn Trong Mảng Sắp XếpSearch Insert Position
Hiểu bài
Cho bạn một mảng số nguyên nums đã sắp xếp tăng dần (không trùng lặp) và số nguyên target. Trả về chỉ số của target nếu tìm thấy. Nếu không, trả về chỉ số mà target sẽ được chèn vào để mảng vẫn còn sắp xếp.
Ví dụ:
nums = [1, 3, 5, 6], target = 5
output = 2 // nums[2] = 5, tìm thấy
nums = [1, 3, 5, 6], target = 2
output = 1 // 2 sẽ chèn vào index 1, giữa 1 và 3
nums = [1, 3, 5, 6], target = 7
output = 4 // 7 sẽ chèn vào cuối mảngĐây là biến thể tìm kiếm nhị phân kinh điển — sau khi vòng lặp kết thúc, low chính là vị trí cần chèn.
Xem cách cơ bản (chậm hơn)
O(n) time, O(1) spacefunction searchInsert(nums: number[], target: number): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) return i
}
return nums.length // target lớn hơn mọi phần tử
}Duyệt tuần tự không khai thác tính chất đã sắp xếp.
Tìm kiếm nhị phân làm được điều tương tự trong O(log n).
Lời giải tối ưu
O(log n) time, O(1) spacefunction searchInsert(nums: number[], target: number): number {
let low = 0
let high = nums.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) low = mid + 1
else high = mid - 1
}
// Khi thoát vòng lặp, low là vị trí chèn đúng
return low
}Cách tối ưu cùng cấu trúc tìm kiếm nhị phân cổ điển, chỉ khác ở giá trị trả về khi không tìm thấy.
Khi vòng lặp kết thúc (low > high), low luôn trỏ vào vị trí đầu tiên lớn hơn target — đó chính là nơi cần chèn.
Chạy thử từng bước
- 1
nums=[1,3,5,6], target=2. low=0, high=3. mid=1, nums[1]=3 > 2 → high=0.
low:0high:3mid:1midVal:3action:"high=0" - 2
low=0, high=0. mid=0, nums[0]=1 < 2 → low=1.
low:0high:0mid:0midVal:1action:"low=1" - 3
low=1 > high=0 → thoát vòng lặp. return low=1.
Đúng: 2 chèn vào index 1.
low:1high:0result:1
Trường hợp biên phải nhớ
Target nhỏ hơn mọi phần tử (nums=[3,5], target=1) — high về -1, low=0 → chèn đầu mảng.
Target lớn hơn mọi phần tử (nums=[1,3], target=5) — low về nums.length → chèn cuối mảng.
Mảng 1 phần tử — chỉ 1 lần so sánh, đủ xác định vị trí.
Target bằng chính xác phần tử đầu hoặc cuối — vẫn trả về chỉ số đúng nhờ điều kiện === trong vòng lặp.