Bỏ qua

Biên tìm kiếm nhị phân

Tìm biên trái

Question

Cho một mảng đã sắp xếp nums có độ dài \(n\) có thể chứa các phần tử trùng lặp, hãy trả về chỉ số của lần xuất hiện ngoài cùng bên trái của target. Nếu mảng không chứa target, trả về \(-1\).

Hãy nhớ lại phương pháp tìm điểm chèn bằng tìm kiếm nhị phân. Sau khi tìm kiếm hoàn tất, \(i\) trỏ đến target ngoài cùng bên trái, vì vậy việc tìm điểm chèn thực chất là tìm chỉ số của target ngoài cùng bên trái.

Hãy cân nhắc việc triển khai tìm kiếm biên trái bằng hàm tìm điểm chèn. Lưu ý rằng mảng có thể không chứa target, dẫn đến hai trường hợp sau:

  • Chỉ số điểm chèn \(i\) vượt quá phạm vi của mảng.
  • Phần tử nums[i] không bằng target.

Khi một trong hai trường hợp này xảy ra, chỉ cần trả về \(-1\). Mã nguồn được hiển thị bên dưới:

[file]{binary_search_edge}-[class]{}-[func]{binary_search_left_edge}

Tìm biên phải

Vậy làm thế nào để tìm được target ngoài cùng bên phải? Cách tiếp cận trực tiếp nhất là sửa đổi mã nguồn và thay thế thao tác thu hẹp con trỏ trong trường hợp nums[m] == target. Mã nguồn ở đây được lược bỏ; độc giả quan tâm có thể tự mình triển khai.

Dưới đây, chúng ta giới thiệu thêm hai phương pháp khéo léo khác.

Tái sử dụng tìm kiếm biên trái

Trên thực tế, chúng ta có thể sử dụng hàm tìm target ngoài cùng bên trái để tìm target ngoài cùng bên phải. Phương pháp cụ thể là: chuyển đổi việc tìm target ngoài cùng bên phải thành tìm target + 1 ngoài cùng bên trái.

Như minh họa trong hình bên dưới, sau khi tìm kiếm hoàn tất, con trỏ \(i\) sẽ trỏ đến target + 1 ngoài cùng bên trái (nếu tồn tại), trong khi \(j\) trỏ đến target ngoài cùng bên phải, do đó chúng ta có thể trả về \(j\).

Chuyển đổi tìm kiếm biên phải thành tìm kiếm biên trái

Lưu ý rằng điểm chèn được trả về là \(i\), vì vậy chúng ta cần trừ đi \(1\) để thu được \(j\):

[file]{binary_search_edge}-[class]{}-[func]{binary_search_right_edge}

Chuyển đổi thành tìm kiếm phần tử

Chúng ta biết rằng khi mảng không chứa target, \(i\) và \(j\) cuối cùng sẽ lần lượt trỏ đến phần tử đầu tiên lớn hơn và phần tử đầu tiên nhỏ hơn target.

Do đó, như minh họa trong hình bên dưới, chúng ta có thể xây dựng một phần tử không tồn tại trong mảng để tìm biên trái và biên phải.

  • Tìm target ngoài cùng bên trái: Có thể chuyển đổi thành tìm kiếm target - 0.5 và trả về con trỏ \(i\).
  • Tìm target ngoài cùng bên phải: Có thể chuyển đổi thành tìm kiếm target + 0.5 và trả về con trỏ \(j\).

Chuyển đổi tìm kiếm biên thành tìm kiếm phần tử

Mã nguồn ở đây được lược bỏ, nhưng có hai điểm sau đây cần lưu ý:

  • Vì mảng đã cho không chứa các giá trị thập phân, chúng ta không cần lo lắng về việc xử lý trường hợp bằng nhau.
  • Do phương pháp này đưa vào số thập phân, biến target trong hàm cần được đổi sang kiểu số thực dấu phẩy động (Python không yêu cầu thay đổi này).