Làm cách nào để hiểu rõ hơn tìm kiếm nhị phân một lần so sánh mỗi lần lặp?

Question

Điểm của tìm kiếm nhị phân một lần so sánh mỗi lần lặp lại là gì? Và bạn có thể giải thích nó hoạt động như thế nào?

Answer 1

Có hai lý do để tìm kiếm nhị phân với một so sánh cho mỗi lần lặp lại. Các ít quan trọng là hiệu suất. Phát hiện kết hợp chính xác sớm bằng cách sử dụng hai so sánhcho mỗi lần lặp lại tiết kiệm một vòng lặp trung bình của vòng lặp, trong khi đó các tìm kiếm nhị phân có liên quan đến một lần so sánh một nửa công việc được thực hiện cho mỗi lần lặp lại.

Tìm kiếm nhị phân một mảng các số nguyên, nó có thể tạo ra sự khác biệt nhỏ một trong hai cách. Ngay cả với một so sánh khá tốn kém, gần như là hiệu suất của là như nhau, và một nửa thay vì-trừ-một trong những có lẽ không phải là giá trị theo đuổi trong nhiều trường hợp. Bên cạnh đó, so sánh đắt tiền thường được mã hóa dưới dạng hàm trả về âm, không hoặc dương cho <, == hoặc >, vì vậy bạn có thể có cả hai so sánh với giá khá nhiều.

Lý do quan trọng để thực hiện tìm kiếm nhị phân với một so sánh trên mỗi lần lặp là vì bạn có thể nhận được nhiều kết quả hữu ích hơn so với chỉ một số đối sánh. Các tìm kiếm chính bạn có thể làm là ...

• chìa khóa đầu tiên> goal
• Đầu tiên chính> = mục tiêu
• chìa khóa đầu tiên == mục tiêu
• cuối chìa khóa < mục tiêu
• cuối chìa khóa < = mục tiêu
• Khóa cuối == mục tiêu

Tất cả đều giảm xuống cùng một thuật toán cơ bản. Hiểu rõ điều này đủ rằng bạn có thể mã tất cả các biến thể dễ dàng không phải là khó khăn, nhưng tôi đã không thực sự nhìn thấy một lời giải thích tốt - chỉ giả mã và chứng minh toán học. là nỗ lực của tôi khi giải thích.

Có những trò chơi mà ý tưởng là để đạt được càng gần nhất có thể đến mục tiêu mà không cần quá tải. Thay đổi điều đó thành "undershooting" và đó là những gì "Tìm kiếm Đầu tiên>". Xem xét các phạm vi ở một số giai đoạn trong quá trình tìm kiếm ...

| lower bound  | goal     | upper bound 
+-----------------+-------------------------+-------------- 
|   Illegal | better   worse | 
+-----------------+-------------------------+-------------- 

Phạm vi giữa giới hạn trên và dưới hiện tại vẫn cần được tìm kiếm. Mục tiêu của chúng tôi là (bình thường) ở đâu đó, nhưng chúng tôi vẫn chưa biết ở đâu. điểm thú vị về các mục ở trên giới hạn trên là chúng hợp pháp trong ý nghĩa rằng chúng lớn hơn mục tiêu. Chúng tôi có thể nói rằng mục chỉ phía trên giới hạn trên hiện tại là giải pháp tốt nhất cho đến nay của chúng tôi. Thậm chí, chúng tôi thậm chí có thể nói điều này ngay từ đầu, mặc dù có thể không có mặt hàng nào ở vị trí đó - theo ý nghĩa , nếu không có giải pháp trong phạm vi hợp lệ, giải pháp tốt nhất chưa được bị từ chối giới hạn trên.

Tại mỗi lần lặp lại, chúng tôi chọn một mục để so sánh giữa giới hạn trên và dưới. Đối với tìm kiếm nhị phân, đó là một mục nửa chiều được làm tròn. Đối với tìm kiếm cây nhị phân, đó là được quyết định bởi cấu trúc của cây. Nguyên tắc cũng giống nhau.

Vì chúng tôi đang tìm kiếm một mục lớn hơn mục tiêu của mình, chúng tôi so sánh mục kiểm tra sử dụng Item [testpos] > goal. Nếu kết quả là sai, chúng tôi có overshot (hoặc undershot) mục tiêu của chúng tôi, vì vậy chúng tôi giữ giải pháp tốt nhất hiện tại của chúng tôi và điều chỉnh giới hạn dưới của chúng tôi trở lên. Nếu kết quả là đúng, chúng tôi đã tìm ra giải pháp mới nhất cho đến nay là , vì vậy chúng tôi điều chỉnh giới hạn trên để phản ánh điều đó. Dù bằng cách nào, chúng tôi không bao giờ muốn so sánh mục kiểm tra đó một lần nữa, vì vậy chúng tôi điều chỉnh ràng buộc để loại bỏ (chỉ riêng) mục thử nghiệm từ phạm vi tìm kiếm. Là bất cẩn với điều này thường dẫn đến các vòng lặp vô hạn.

Thông thường, phạm vi nửa mở được sử dụng - một giới hạn dưới bao gồm và một giới hạn trên độc quyền. Sử dụng hệ thống này, mục ở chỉ mục giới hạn trên không nằm trong phạm vi tìm kiếm (ít nhất là không phải bây giờ), nhưng nó là là giải pháp tốt nhất cho đến nay. Khi bạn di chuyển giới hạn dưới lên, bạn di chuyển nó đến testpos+1 (để loại trừ mục bạn chỉ cần thử nghiệm từ phạm vi). Khi bạn di chuyển giới hạn trên xuống, bạn di chuyển nó đến testpos (giới hạn trên là độc quyền anyway).

if (item[testpos] > goal) 
{ 
    // new best-so-far 
    upperbound = testpos; 
} 
else 
{ 
    lowerbound = testpos + 1; 
} 

Khi phạm vi giữa cận dưới và phía trên là rỗng (sử dụng nửa mở, khi cả hai đều có chỉ số giống nhau), kết quả của bạn là giải pháp tốt nhất-so-xa gần đây nhất của bạn, ngay trên của bạn giới hạn trên (ví dụ: chỉ số giới hạn trên cho nửa mở).

Vì vậy, toàn bộ thuật toán là ...

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far 
    upperbound = testpos; 
    } 
    else 
    { 
    lowerbound = testpos + 1; 
    } 
} 

Để thay đổi từ first key > goal để first key >= goal, bạn có nghĩa là chuyển các toán tử so sánh trong dòng if. Toán tử tương đối và mục tiêu có thể được thay thế bằng một tham số duy nhất - một hàm vị ngữ trả về true nếu (và chỉ nếu) tham số của nó nằm ở phía lớn hơn của mục tiêu.

Điều đó cung cấp cho bạn "đầu tiên" và "đầu tiên> =". Để nhận được "first ==", hãy sử dụng "first> =" và thêm kiểm tra bình đẳng sau khi thoát khỏi vòng lặp.

Đối với "số <" cuối cùng, v.v., nguyên tắc giống như trên, nhưng phạm vi là được phản ánh. Điều này chỉ có nghĩa là bạn trao đổi qua các điều chỉnh bị ràng buộc (nhưng không phải là nhận xét ) cũng như thay đổi toán tử. Nhưng trước khi thực hiện điều đó, hãy xem xét những điều sau ...

a > b == !(a <= b) 
a >= b == !(a < b) 

Ngoài ra ...

• vị trí (cuối cùng chốt < khung thành) = vị trí (đầu tiên quan trọng> = khung thành) - 1
• vị trí (cuối cùng chốt < = khung thành) = vị trí (key đầu tiên> khung thành) - 1

Khi chúng tôi di chuyển giới hạn của chúng tôi trong quá trình tìm kiếm, cả hai bên đang được di chuyển về phía mục tiêu cho đến khi họ gặp nhau tại mục tiêu. Và có một mặt hàng đặc biệt ngay dưới giới hạn dưới, giống như chỉ ở trên giới hạn trên ...

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far for first key > goal at [upperbound] 
    upperbound = testpos; 
    } 
    else 
    { 
    // new best-so-far for last key <= goal at [lowerbound - 1] 
    lowerbound = testpos + 1; 
    } 
} 

Vì vậy, theo cách nào đó, chúng tôi có hai tìm kiếm bổ sung chạy cùng một lúc. Khi cuộc họp trên và xuống dưới, chúng tôi có kết quả tìm kiếm hữu ích ở mỗi bên của đường biên đơn đó.

Đối với tất cả các trường hợp, có khả năng rằng một "tưởng tượng" gốc ngoài phạm vi vị trí tốt nhất cho đến nay là kết quả cuối cùng của bạn (không có kết quả nào trong phạm vi tìm kiếm ). Điều này cần phải được kiểm tra trước khi thực hiện kiểm tra cuối cùng == cho các trường hợp đầu tiên == và cuối cùng ==. Đó cũng có thể là hành vi hữu ích - ví dụ: nếu bạn đang tìm kiếm vị trí để chèn mục tiêu của mình, hãy thêm nó sau khi kết thúc các mục hiện tại của bạn là điều đúng đắn nếu tất cả các mục hiện có nhỏ hơn mục tiêu của bạn.

Một vài ghi chú về sự lựa chọn của testpos ...

testpos = lowerbound + ((upperbound-lowerbound)/2); 

Trước hết, điều này sẽ không bao giờ tràn, không giống như rõ ràng hơn ((lowerbound + upperbound)/2). Nó cũng hoạt động với con trỏ cũng như số nguyên chỉ mục.

Thứ hai, phân chia được giả định là làm tròn xuống. Làm tròn xuống cho số âm không là OK (tất cả các bạn có thể chắc chắn trong C) vì sự khác biệt luôn luôn là không tiêu cực anyway.

Đây là một khía cạnh có thể cần quan tâm nếu bạn sử dụng các phạm vi không mở một nửa , đảm bảo vị trí kiểm tra nằm trong phạm vi tìm kiếm chứ không phải bên ngoài (trên một trong những giá trị đã tìm thấy tốt nhất) vị trí cho đến nay).

Cuối cùng, trong một tìm kiếm cây nhị phân, di chuyển giới hạn là tiềm ẩn và sự lựa chọn của testpos được xây dựng vào cấu trúc của cây (có thể không cân bằng), nhưng các nguyên tắc tương tự áp dụng cho những gì tìm kiếm là đang làm. Trong trường hợp này, chúng tôi chọn nút con của chúng tôi để thu hẹp phạm vi tiềm ẩn. Đối với các trận đấu đầu tiên trường hợp, hoặc là chúng tôi đã tìm thấy một trận đấu nhỏ hơn mới tốt nhất (đi đến trẻ thấp hơn với hy vọng tìm kiếm thậm chí nhỏ hơn và tốt hơn) hoặc chúng tôi đã vượt qua (đi đến đứa trẻ cao hơn với hy vọng phục hồi). Một lần nữa, bốn trường hợp chính có thể được xử lý bằng cách chuyển đổi toán tử so sánh.

BTW - có nhiều toán tử có thể sử dụng hơn cho thông số mẫu đó. Xem xét một mảng được sắp xếp theo năm sau đó tháng. Có thể bạn muốn tìm mục đầu tiên cho một năm cụ thể. Để thực hiện việc này, hãy viết hàm so sánh so với năm và bỏ qua tháng - mục tiêu so sánh như nhau nếu năm bằng nhau, nhưng giá trị mục tiêu có thể là một loại khác với khóa thậm chí không có giá trị tháng so sánh. Tôi nghĩ về điều này như là một "so sánh một phần chính", và cắm nó vào mẫu tìm kiếm nhị phân của bạn và bạn nhận được những gì tôi nghĩ là một "tìm kiếm khóa một phần".

CHỈNH SỬA Đoạn dưới đây được sử dụng để nói "ngày 31 tháng 12 năm 1999 sẽ bằng 1 tháng 2 năm 2000". Điều đó sẽ không hoạt động trừ khi toàn bộ phạm vi ở giữa cũng được coi là bình đẳng. Vấn đề là cả ba phần của ngày bắt đầu và kết thúc phạm vi đều khác nhau, vì vậy bạn không phải đối phó với khóa "một phần", nhưng các khóa được coi là tương đương cho tìm kiếm phải tạo thành một khối liền kề trong vùng chứa, thường sẽ ngụ ý một khối tiếp giáp trong bộ khóa có thể đặt hàng.

Nó cũng không chỉ là các phím "một phần". So sánh tùy chỉnh của bạn có thể xem xét ngày 31 tháng 12 năm 1999 bằng 1 tháng 1 năm 2000, nhưng tất cả các ngày khác đều khác nhau. Vấn đề là so sánh tùy chỉnh phải đồng ý với khóa ban đầu về thứ tự, nhưng nó có thể không quá cầu kỳ về việc xem xét tất cả các giá trị khác nhau - nó có thể xử lý một loạt các khóa như một "lớp tương đương".

---

Lưu ý thêm về giới hạn mà tôi thực sự nên bao gồm trước đây, nhưng tôi có thể không nghĩ về cách này vào thời điểm đó.

Một cách suy nghĩ về giới hạn là chúng không phải là chỉ số mục. Một ràng buộc là đường ranh giới giữa hai mặt hàng, do đó bạn có thể đánh số các đường ranh giới dễ dàng như bạn có thể đánh số các mặt hàng ...

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 

Rõ ràng việc đánh số giới hạn liên quan đến việc đánh số các mặt hàng. Miễn là bạn đánh số giới hạn của bạn từ trái sang phải và giống như cách bạn đánh số các mục của bạn (trong trường hợp này bắt đầu từ số không) kết quả có hiệu quả giống như quy ước nửa mở thông thường.

Có thể chọn một giới hạn ở giữa để chia đôi phạm vi chính xác thành hai, nhưng đó không phải là điều mà tìm kiếm nhị phân thực hiện. Đối với tìm kiếm nhị phân, bạn chọn một mục để kiểm tra - không phải là một ràng buộc. Mục đó sẽ được kiểm tra trong lần lặp này và không bao giờ được kiểm tra lại, vì vậy nó bị loại trừ khỏi cả hai phần phụ.

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 
         ^
     |<-------------------|------------->| 
          | 
     |<--------------->| | |<--------->| 
      low range  i  hi range 

Vì vậy, các testpos và testpos+1 trong thuật toán là hai trường hợp dịch chỉ số mục vào chỉ số ràng buộc. Tất nhiên nếu hai giới hạn là bằng nhau, không có mục nào trong phạm vi đó để chọn vì vậy vòng lặp không thể tiếp tục, và kết quả duy nhất có thể là một giá trị bị ràng buộc.

Phạm vi được hiển thị ở trên chỉ là phạm vi vẫn được tìm kiếm - khoảng cách chúng tôi dự định đóng giữa các dải đã được chứng minh thấp hơn và đã được chứng minh.

Trong mô hình này, tìm kiếm nhị phân đang tìm kiếm ranh giới giữa hai loại giá trị đã đặt hàng - các loại được xếp loại là "thấp hơn" và các loại được xếp hạng là "cao hơn". Bài kiểm tra biến vị ngữ phân loại một mục. Không có lớp "bằng nhau" - giá trị bằng với khóa là một phần của lớp cao hơn (đối với x[i] >= key) hoặc lớp thấp hơn (cho x[i] > key).