Cho một mảng các số nguyên phân biệt đã được sắp xếp tăng dần nums và một giá trị target. Hãy trả về chỉ số nếu tìm thấy target. Nếu không tìm thấy, hãy trả về chỉ số nơi nó sẽ được chèn vào theo đúng thứ tự sắp xếp.
Yêu cầu: Độ phức tạp thời gian đạt O(log n).
Ví dụ 1: nums = [1, 3, 5, 6], target = 5 -> 2
Ví dụ 2: nums = [1, 3, 5, 6], target = 2 -> 1
Định Dạng Đầu Vào (Input)
Dòng 1: Mảng nums
Dòng 2: Số nguyên target
Dòng 2: Số nguyên target
Định Dạng Đầu Ra (Output)
Chỉ số nguyên (index)
Ràng Buộc (Constraints)
1 <= nums.length <= 10^4
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1, 3, 5, 6]
5
Output:
2
Giải thích: 5 có tại index 2
Ví dụ 2:
Input:
[1, 3, 5, 6]
2
Output:
1
Giải thích: Chèn 2 vào index 1
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Binary Search Vị Trí Chèn O(log n)
Khi vòng lặp nhị phân kết thúc (left > right), biến left chính là chỉ số vị trí chèn hợp lệ.
Dữ liệu đầu vào (Input):
[1, 3, 5, 6]
5
Kết quả kỳ vọng (Expected Output):
2
Dữ liệu đầu vào (Input):
[1, 3, 5, 6]
2
Kết quả kỳ vọng (Expected Output):
1
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
