Lập trình Pearls Sự cố: Kiểm tra mảng đã sắp xếp trong tìm kiếm nhị phân

Question

Trong Programming Pearls (ấn bản thứ hai) Cột 5, vấn đề 5 là câu hỏi về triển khai tìm kiếm nhị phân trên mảng chưa được sắp xếp.

Làm cách nào bạn có thể thêm kiểm tra từng phần vào chức năng ở mức ít hơn đáng kể so với chi phí O (n-1)?

Tôi biết bạn có thể kiểm tra với mọi lần lặp và đạt được O (log n), nhưng gợi ý ở phía sau gợi ý có giải pháp O (1).

Giải pháp đó là gì?

Answer 1

Tóm tắt

một phần kiểm tra nếu mảng được sắp xếp sao cho việc tìm kiếm nhị phân được áp dụng có thể được thực hiện trong thời gian O (log n), như OP nói, và trong thời gian O (1). Phương pháp O (log n) là kiểm tra từng đầu dò đối với đầu dò trước đó để đảm bảo rằng nó so sánh đúng (nhỏ hơn, lớn hơn). Phương pháp O (1) là chỉ kiểm tra phần tử cuối cùng được tìm thấy bằng tìm kiếm nhị phân và một bên cạnh nó để tìm thấy nếu phần tử tìm kiếm sau không được tìm thấy, ít nhất là địa điểm chính xác để chèn được tìm thấy. Nếu tìm thấy yếu tố tìm kiếm sau đó, thì đó là kiểm tra một phần O (1) tốt.

Còn giải thích

Các phần của vấn đề trước khi khối mã nói rằng một vấn đề phổ biến là sử dụng tìm kiếm nhị phân trên một mảng được phân loại. Về cơ bản, làm thế nào có thể sử dụng một phần kiểm tra để kiểm tra xem một mảng được sắp xếp trong ít hơn O (n-1) chi phí?

Giải pháp O (log n) là kiểm tra từng đầu dò dò tìm nhị phân đối với đầu dò trước đó (nhỏ hơn hoặc lớn hơn mong đợi). Điều này không đảm bảo rằng mảng được sắp xếp, nhưng nó là một phần kiểm tra tốt.

Kiểm tra O (1) duy nhất mà tôi có thể nghĩ là kiểm tra vị trí cuối cùng được tìm kiếm sao cho giá trị của nó và các giá trị lân cận lưới với ý tưởng về phần tử tìm kiếm, ngay cả khi phần tử không tìm thấy. Đó là một phần kiểm tra khá tốt: nếu phần tử được tìm thấy thì mọi thứ có thể hoạt động chính xác. Nếu không, sau đó kiểm tra các phần tử xung quanh vị trí của nó để có phần tử nhỏ hơn phần tử tìm kiếm và sau đó phần tử lớn hơn phần tử tìm kiếm. Tuy nhiên, tôi nhận ra rằng việc kiểm tra theo cách này có nghĩa là tìm kiếm nhị phân, là O (log n), đã được thực hiện nên tôi không biết đây có phải là O (1) hay không. Tuy nhiên, nó chỉ thêm O (1) vào tìm kiếm tổng thể vì vậy tôi nghĩ rằng nó có thể áp dụng được.