Tìm kiếm nhị phân đệ quy và miền rỗng

A đã được sắp xếp không giảm. Hàm tìm giá trị K trong miền từ left tới right, gồm cả hai đầu. Nếu tìm thấy, trả một chỉ số i có A[i]==K; nếu không có, trả −1. Nếu có nhiều giá trị bằng K, thuật toán dưới đây chỉ cần trả một vị trí, không hứa là vị trí đầu tiên. Đầu tiên gọi với left=0, right=len(A)−1. Khi left>right, miền rỗng nên trả −1 trước khi đọc A[mid]. Khi còn phần tử, so sánh phần tử giữa với K để chỉ tìm tiếp một phía.

```python def tim_nhi_phan(A, left, right, K): if left > right: return -1 mid = (left + right) // 2 if A[mid] == K: return mid if A[mid] < K: return tim_nhi_phan( A, mid + 1, right, K) return tim_nhi_phan( A, left, mid - 1, K) ``` Nếu A[mid]<K thì cả phần bên trái và phần tử giữa không thể là kết quả; tìm tiếp từ mid+1. Nếu A[mid]>K thì tìm bên trái tới mid−1. Hai cách đều thu hẹp miền. Return ở lời gọi tiếp chuyển kết quả tìm được về nơi gọi ban đầu.

Với A rỗng, lời gọi đầu dùng left=0, right=−1. Chỉ kiểm left==right sẽ bỏ sót trường hợp này; cần kiểm miền rỗng trước khi truy cập A. Cũng có thể thiết kế một biến thể dừng riêng khi left==right, rồi giữ mid trong nhánh trái. Với biến thể ấy vẫn cần nhánh left>right để xử lí A rỗng. Không đổi tùy ý mid−1 thành mid trong chương trình đang dùng nếu chưa kiểm lại cách thu hẹp miền và cơ sở.