C# Danh sách <T>. Giá trị trả về tìm kiếm nhị phân khi giá trị không tìm thấy

Question

Tôi đang nhầm lẫn về phương pháp tìm kiếm nhị phân List<T> trong trường hợp mục không tồn tại.

Tôi đã có

List<long> theList = {1, 3, 5, ...}. 

theList.BInarySearch(0) trả về 0, và theList.BInarySearch(3) lợi nhuận 1, như mong đợi.

Tuy nhiên, theList.BinarySearch(1) trả về -2 và không phải -1 như tôi mong đợi. Hướng dẫn sử dụng MSDN cho biết: "Giá trị trả về: Chỉ mục dựa trên số không trong danh sách được sắp xếp, nếu mục được tìm thấy, nếu không, số âm là phần bổ sung bit của chỉ mục của phần tử tiếp theo lớn hơn mục hoặc , nếu không có phần tử lớn hơn, thì bổ sung bit của Count. "

Một "bổ sung bit"? Tôi đang thiếu gì ở đây và tại sao lại là theList.BinarySearch(1) != -1?

Answer 1

đầu tiên - tại sao bạn mong chờ -1? Nếu mục là mục đầu tiên, nó không thể trả về -0 (cho số nguyên), do đó, nó đứng để lý do -2 sẽ được trả lại cho mục thứ hai.

Tiếp theo, bạn có thể dễ dàng lấy chỉ mục phù hợp bằng cách sử dụng ~-2 - toán tử bitwise không.

Answer 2

Để chuyển nó đến một điểm chèn, đi Bitwise bổ sung, đó là: ~retval

Answer 3

Tôi giả sử bạn đang nói về theList.BinarySearch(2), bởi vì 1 tồn tại và giá trị trả về phải là 0.

bitwise complement operator không tạo ra tác dụng tương tự như phủ nhận số nguyên, mà tôi nghĩ là nguồn gốc của sự nhầm lẫn của bạn. Trong mọi trường hợp, bạn không cần phải hiểu cách toán tử hoạt động để phân nhánh chính xác trên kết quả tìm kiếm; đoạn MSDN trong câu hỏi của bạn, và thực tế là ~~a = a, trực tiếp ám chỉ đoạn này:

int index = theList.BinarySearch(num); 

if (index >= 0) 
{ 
    //exists 
    ... 
} 
else 
{ 
    // doesn't exist 
    int indexOfBiggerNeighbour = ~index; //bitwise complement of the return value 

    if (indexOfBiggerNeighbour == theList.Count) 
    { 
     // bigger than all elements 
     ... 
    } 

    else if (indexOfBiggerNeighbour == 0) 
    { 
     // smaller than all elements 
     ... 
    } 

    else 
    { 
     // Between 2 elements 
     int indexOfSmallerNeighbour = indexOfBiggerNeighbour - 1; 
     ... 
    } 
} 

Answer 4

Lý do trả lại những chỉ số tiêu cực là để hỗ trợ chèn các mục mà không được tìm thấy vào danh sách. Trong ví dụ này, 2 sẽ được chèn vào chỉ mục = 2. Nếu không, bạn sẽ phải thực hiện tìm kiếm nhị phân khác để tìm vị trí đó.