/** Return an index of x in a.
* Requires: a is sorted in ascending order, and x is found in the array a
* somewhere between indices left and right.
*/
int binsrch(int x, int[] a, int left, int right) {
while (true) {
int m = (left+right)/2;
if (x == a[m]) return m;
if (x < a[m])
r = m−1;
else
l = m+1;
}
}
Quan sát chính là binsrch hoạt động theo kiểu phân chia và chinh phục, tự gọi chỉ trên các đối số "nhỏ hơn" theo một cách nào đó.
Cho P (n) là xác nhận rằng binsrch hoạt động chính xác cho các đầu vào trong đó phải − left = n. Nếu chúng ta có thể chứng minh rằng P (n) là đúng cho tất cả n, thì chúng ta biết rằng binsrch hoạt động trên tất cả các đối số có thể.
Trường hợp cơ bản. Trong trường hợp n = 0, chúng ta biết left = right = m. Vì chúng ta giả định rằng hàm sẽ chỉ được gọi khi x được tìm thấy giữa trái và phải, nó phải là trường hợp x = a [m], và do đó hàm sẽ trả về m, một chỉ mục của x trong mảng a.
Bước quy nạp. Chúng tôi giả định rằng binsrch hoạt động miễn là trái − phải ≤ k. Mục tiêu của chúng tôi là chứng minh rằng nó hoạt động trên đầu vào bên trái − bên phải = k + 1. Có ba trường hợp, trong đó x = a [m], trong đó x < a [m] và trong đó x> a [m].
Case x = a[m]. Clearly the function works correctly.
Case x < a[m]. We know because the array is sorted that x must be found between a[left] and a[m-1]. The n for the recursive call is n = m − 1 − left = ⌊(left+right)/2⌋ − 1 − left. (Note that ⌊x⌋ is the floor of x, which rounds it down toward negative infinity.) If left+right is odd, then n = (left + right − 1)/2 − 1 − left = (right − left)/2 − 1, which is definitely smaller than right−left. If left+right is even then n = (left + right)/2 − 1 − left = (right−left)/2, which is also smaller than k + 1 = right−left because right−left = k + 1 > 0. So the recursive call must be to a range of a that is between 0 and k cells, and must be correct by our induction hypothesis.
Case x > a[m]. This is more or less symmetrical to the previous case. We need to show that r − (m + 1) ≤ right − left. We have r − (m + 1) − l = right − ⌊(left + right)/2⌋ − 1. If right+left is even, this is (right−left)/2 − 1, which is less than right−left. If right+left is odd, this is right− (left + right − 1)/2 − 1 = (right−left)/2 − 1/2, which is also less than right−left. Therefore, the recursive call is to a smaller range of the array and can be assumed to work correctly by the induction hypothesis.
Vì trong mọi trường hợp, quy trình bước quy nạp đều có thể kết luận rằng binsrch (và biến thể lặp lại của nó) là chính xác!
Lưu ý rằng nếu chúng tôi đã nhầm lẫn mã hóa trường hợp x> a [m] và chuyển m sang trái thay vì m + 1 (dễ thực hiện!), Bằng chứng chúng tôi vừa tạo sẽ không thành công trong trường hợp đó . Và trên thực tế, thuật toán có thể đi vào vòng lặp vô hạn khi phải = trái + 1. Điều này cho thấy giá trị của lý luận quy nạp cẩn thận.
tham khảo: http://www.cs.cornell.edu/Courses/cs211/2006sp/Lectures/L06-Induction/binary_search.html