Tính trung trong tìm kiếm nhị phân

Question

Tôi đã đọc một cuốn sách thuật toán trong đó có thuật toán sau đây để tìm kiếm nhị phân:

public class BinSearch { 
    static int search (int [ ] A, int K) { 
    int l = 0 ; 
    int u = A. length −1; 
    int m; 
    while (l <= u) { 
     m = (l+u) /2; 
     if (A[m] < K) { 
     l = m + 1 ; 
     } else if (A[m] == K) { 
     return m; 
     } else { 
      u = m−1; 
     } 
     } 
     return −1; 
     } 
} 

Tác giả nói "Lỗi này là ở sự phân công m = (l+u)/2; nó có thể dẫn đến tràn và nên được thay thế bởi m = l + (u-l)/2. "

Tôi không thể thấy điều đó có thể gây tràn. Khi tôi chạy thuật toán trong tâm trí của tôi cho một vài đầu vào khác nhau, tôi không thấy giá trị của giữa đi ra khỏi chỉ mục mảng.

Vì vậy, trong trường hợp nào xảy ra tràn?

Answer 1

Điều này post bao gồm lỗi nổi tiếng này trong rất nhiều chi tiết. Như những người khác đã nói đó là một vấn đề tràn. Việc sửa chữa đề nghị vào liên kết như sau:

int mid = low + ((high - low)/2); 

// Alternatively 
int mid = (low + high) >>> 1; 

Nó cũng có lẽ là đáng nói rằng trong trường hợp chỉ số tiêu cực được cho phép, hoặc có lẽ nó thậm chí không một mảng đang được tìm kiếm (ví dụ, tìm kiếm một giá trị trong một số dãy số nguyên đáp ứng một số điều kiện), mã ở trên có thể không chính xác. Trong trường hợp này, điều gì đó xấu xí như

(low < 0 && high > 0) ? (low + high)/2 : low + (high - low)/2 

có thể cần thiết. Một ví dụ tốt là searching for the median in an unsorted array without modifying it or using additional space bằng cách thực hiện tìm kiếm nhị phân trên toàn bộ phạm vi Integer.MIN_VALUE - Integer.MAX_VALUE.

Answer 2

Lỗi tràn tiềm năng nằm trong chính việc tự thêm l+u.

Đây thực sự là a bug in early versions tìm kiếm nhị phân trong JDK.

Answer 3

Vấn đề là (l+u) được đánh giá trước và có thể tràn int, vì vậy (l+u)/2 sẽ trả về giá trị sai.

Answer 4

Jeff đề xuất thực sự tốt post để đọc về lỗi này, dưới đây là tóm tắt nếu bạn muốn tổng quan nhanh.

Trong lập trình ngọc trai Bentley nói rằng dòng tương tự "đặt m đến mức trung bình của l và u, cắt ngắn xuống số nguyên gần nhất." Trên khuôn mặt của nó, xác nhận này có thể xuất hiện chính xác, nhưng nó không thành công cho các giá trị lớn của các biến int thấp và cao. Cụ thể, nó không thành công nếu tổng giá trị thấp và cao lớn hơn giá trị int dương lớn nhất (2^31 - 1). Tổng số tiền tràn vào giá trị âm và giá trị vẫn âm khi chia cho hai. Trong C, điều này gây ra một chỉ mục mảng ngoài giới hạn với kết quả không thể đoán trước. Trong Java, nó ném ArrayIndexOutOfBoundsException.