Binary search là gì


Cách Binary Search có tác dụng việc

Để Binary Search thao tác thì mảng buộc phải cần được sắp xếp. Để nhân thể cho vấn đề theo dõi, mình sẽ cung cấp thêm các hình minh họa tương ứng với mỗi bước.

Giả sử họ phải search địa điểm của quý hiếm 31 trong một mảng bao gồm những cực hiếm nhỏng hình dưới đây do sử dụng Binary Search:

*

trước hết, bọn họ chia mảng thành hai nửa theo phnghiền toán thù sau:

Output:


Với ví dụ bên trên là 0 + (9 – 0)/ 2 = 4 (giá trị là 4.5). Do đó 4 là chỉ mục giữa của mảng.

Bạn đang xem: Binary search là gì

*

Bây tiếng chúng ta so sánh giá trị thành phần thân với phần tử bắt buộc tra cứu. Giá trị bộ phận thân là 27 và thành phần phải tra cứu là 31, cho nên vì vậy là không liên kết. Bởi vày giá trị phải kiếm tìm là to hơn nên phần tử bắt buộc kiếm tìm đã nằm ở mảng nhỏ mặt đề nghị bộ phận thân.

*

Chúng ta thay đổi quý giá ban-đầu thành chỉ-mục-thân + 1 với lại thường xuyên tìm tìm cực hiếm chỉ-mục-giữa.

Output:


Bây giờ chỉ mục giữa của chúng ta là 7. Chúng ta đối chiếu quý hiếm trên chỉ mục này với giá trị buộc phải tìm.

*

Giá trị trên chỉ mục 7 là không kết nối, với Nhiều hơn quý hiếm bắt buộc tìm kiếm là nhỏ tuổi hơn quý hiếm tại chỉ mục 7 vì vậy bọn họ bắt buộc tìm trong mảng con phía trái của chỉ mục giữa này.

Xem thêm: Bioinformatics Là Gì ? Tổng Quan Về Tin Sinh Học

*

Tiếp tục tìm kiếm chỉ-mục-thân lần tiếp nữa. Lần này nó có giá trị là 5.

*

So sánh cực hiếm tại chỉ mục 5 với cái giá trị phải kiếm tìm với thấy rằng nó kết nối.

*

Do kia chúng ta tóm lại rằng quý giá yêu cầu tìm 31 được giữ giàng trên địa chỉ chỉ mục 5.

Xem thêm: Nt Là Gì ? Nt Nghĩa Là Gì

Binary Search phân chia song lượng thành phần buộc phải tra cứu với cho nên vì vậy sút số lượng phép so sánh đề xuất tiến hành nên giải mã tra cứu kiếm này được tiến hành tương đối nhanh.

Giải thuật mẫu mã đến Binary Search

Dưới đấy là code chủng loại mang lại lời giải search tìm nhị phân:


Chuyên mục: Blockchain