Điểm chèn của tìm kiếm nhị phân

Tìm kiếm nhị phân không chỉ được dùng để tìm kiếm các phần tử mục tiêu, mà còn có thể giải quyết nhiều bài toán biến thể, chẳng hạn như tìm kiếm vị trí chèn của một phần tử mục tiêu.

Trường hợp không có phần tử trùng lặp

Question

Cho một mảng đã sắp xếp nums có độ dài \(n\) và một phần tử target, trong đó mảng không chứa các phần tử trùng lặp, hãy chèn target vào nums sao cho vẫn duy trì trật tự đã sắp xếp của nó. Nếu target đã tồn tại trong mảng, hãy chèn nó vào bên trái của phần tử đó. Trả về chỉ số của target sau khi chèn. Một ví dụ được hiển thị dưới đây.

Nếu muốn tái sử dụng mã nguồn tìm kiếm nhị phân từ phần trước, chúng ta cần trả lời hai câu hỏi sau.

Câu hỏi 1: Khi mảng chứa target, chỉ số của điểm chèn có giống với chỉ số của phần tử đó không?

Bài toán yêu cầu chèn target vào bên trái của các phần tử bằng nó, điều này có nghĩa là target mới được chèn sẽ thay thế vị trí của target ban đầu. Nói cách khác, khi mảng chứa target, chỉ số của điểm chèn chính là chỉ số của target đó.

Câu hỏi 2: Khi mảng không chứa target, chỉ số của điểm chèn là gì?

Để phân tích kỹ hơn điều này, hãy xem xét quá trình tìm kiếm nhị phân: khi nums[m] < target, \(i\) di chuyển, nghĩa là con trỏ \(i\) đang tiếp cận các phần tử lớn hơn hoặc bằng target. Tương tự, con trỏ \(j\) luôn tiếp cận các phần tử nhỏ hơn hoặc bằng target.

Do đó, khi tìm kiếm nhị phân kết thúc, \(i\) phải trỏ đến phần tử đầu tiên lớn hơn target, và \(j\) phải trỏ đến phần tử đầu tiên nhỏ hơn target. Từ đó suy ra khi mảng không chứa target, chỉ số của điểm chèn chính là \(i\). Mã nguồn được hiển thị bên dưới:

[file]{binary_search_insertion}-[class]{}-[func]{binary_search_insertion_simple}

Trường hợp có phần tử trùng lặp

Question

Dựa trên bài toán trước, giả sử mảng có thể chứa các phần tử trùng lặp, các điều kiện khác giữ nguyên.

Giả sử có nhiều phần tử target trong mảng. Tìm kiếm nhị phân thông thường chỉ có thể trả về chỉ số của một target nào đó, và không thể xác định có bao nhiêu phần tử target ở bên trái và bên phải của phần tử đó.

Bài toán yêu cầu chèn phần tử mục tiêu vào vị trí ngoài cùng bên trái, vì vậy chúng ta cần tìm chỉ số của target ngoài cùng bên trái trong mảng. Một cách tiếp cận ban đầu trực quan là thực hiện theo các bước hiển thị trong hình bên dưới:

1. Thực hiện tìm kiếm nhị phân để lấy chỉ số của một target bất kỳ, ký hiệu là \(k\).
2. Bắt đầu từ chỉ số \(k\), thực hiện duyệt tuyến tính sang bên trái, và trả về kết quả khi tìm thấy target ngoài cùng bên trái.

Mặc dù phương pháp này hoạt động được, nó bao gồm tìm kiếm tuyến tính, dẫn đến độ phức tạp thời gian là \(O(n)\). Khi mảng chứa nhiều phần tử target trùng lặp, phương pháp này rất kém hiệu quả.

Bây giờ hãy cân nhắc việc mở rộng mã nguồn tìm kiếm nhị phân. Như được hiển thị trong hình dưới đây, quy trình tổng thể không thay đổi: trong mỗi vòng lặp, trước tiên chúng ta tính chỉ số trung điểm \(m\), sau đó so sánh target với nums[m], dẫn đến các trường hợp sau:

• Khi nums[m] < target hoặc nums[m] > target, nghĩa là vẫn chưa tìm thấy target, vì vậy hãy sử dụng thao tác thu hẹp khoảng tiêu chuẩn của tìm kiếm nhị phân để di chuyển hai con trỏ \(i\) và \(j\) lại gần target hơn.
• Khi nums[m] == target, nghĩa là các phần tử nhỏ hơn target nằm trong khoảng \([i, m - 1]\), vì vậy hãy sử dụng \(j = m - 1\) để thu hẹp khoảng, từ đó di chuyển con trỏ \(j\) lại gần hơn với các phần tử nhỏ hơn target.

Sau khi vòng lặp kết thúc, \(i\) trỏ đến target ngoài cùng bên trái, và \(j\) trỏ đến phần tử đầu tiên nhỏ hơn target, do đó chỉ số \(i\) chính là điểm chèn.

<1><2><3><4><5><6><7><8>

Hãy quan sát mã nguồn dưới đây: các nhánh nums[m] > target và nums[m] == target thực hiện cùng một thao tác, do đó chúng có thể được gộp lại làm một.

Mặc dù vậy, chúng ta vẫn có thể triển khai chi tiết các nhánh điều kiện, vì điều này giúp logic trở nên rõ ràng và dễ đọc hơn.

[file]{binary_search_insertion}-[class]{}-[func]{binary_search_insertion}

Tip

Mã nguồn trong phần này hoàn toàn sử dụng phương pháp "khoảng đóng". Độc giả quan tâm có thể tự mình triển khai theo phương pháp "đóng trái mở phải".

Nhìn chung, tìm kiếm nhị phân chỉ đơn giản là việc thiết lập các mục tiêu tìm kiếm riêng biệt cho hai con trỏ \(i\) và \(j\). Mục tiêu có thể là một phần tử cụ thể (chẳng hạn như target) hoặc một phạm vi phần tử (chẳng hạn như các phần tử nhỏ hơn target).

Với mỗi vòng lặp của tìm kiếm nhị phân, các con trỏ \(i\) và \(j\) sẽ dần tiếp cận các mục tiêu đã đặt trước của chúng. Cuối cùng, chúng sẽ tìm thấy câu trả lời hoặc dừng lại sau khi vượt qua ranh giới.