Tìm kiếm nhị phân không chỉ được sử dụng để tìm các phần tử trong mảng mà còn để tìm nghiệm của các phương trình và giá trị của các hàm đơn điệu (tăng hoặc giảm).
Hãy cho chúng ta một hàm đơn điệu
f và một số giá trị
C của hàm này. Tìm giá trị của đối số
x của hàm này sao cho
\(f(x)=C\).
Ví dụ về hàm đơn điệu tăng:
Chúng tôi chọn các ranh giới như vậy trong đó giá trị của hàm chính xác lớn hơn và chính xác nhỏ hơn giá trị đã cho. Hãy chọn giá trị ở giữa phân khúc này. Nếu nó nhỏ hơn giá trị đã cho, thì chúng ta dịch chuyển đường viền bên trái vào giữa đoạn. Nếu không, chúng tôi sẽ dịch chuyển đường viền bên phải. Tiếp theo, chúng tôi lặp lại quá trình thu hẹp ranh giới. Nhưng có một vấn đề là khi nào thì ngừng tìm kiếm. Đọc thêm
tại đây.
Ví dụ, xét bài toán tìm căn bậc hai của số x. Căn bậc hai của x (ký hiệu là \(\sqrt x\)) là một số y sao cho < span class="math-tex">\(y^2 = x\).
Hãy lập công thức bài toán như sau: với một số thực
x (
\(x >= 1\)) cho trước căn bậc hai với độ chính xác không nhỏ hơn 5 ký tự sau dấu chấm.
Chọn đường viền của đoạn để tìm kiếm
Vì chúng ta không thể kiểm tra toàn bộ vô số số nên chúng ta cần xác định ranh giới của việc tìm kiếm gốc. Đầu tiên, hãy tìm đường viền bên trái, chọn một điểm âm tùy ý (ví dụ: -1). Chúng tôi sẽ nhân đôi nó cho đến khi giá trị trong đó lớn hơn giá trị đã cho. Để tìm đúng biên ta chọn một điểm dương tùy ý (ví dụ: 1). Chúng tôi sẽ nhân đôi nó cho đến khi giá trị của hàm tại thời điểm này nhỏ hơn giá trị đã chỉ định.
Hoặc, nếu biết chính xác ranh giới tìm kiếm, chúng ta có thể lấy 1 làm ranh giới bên trái và chính số đó
x.
Sau đó, ta chia đôi đoạn hiện tại, lấy bình phương ở giữa, nếu lớn hơn x thì thay mặt trên, ngược lại dưới cùng.
Triển khai cuối cùng: