Thuật Toán Binary Search Là Gì, Giải Thuật Tìm Kiếm Nhị Phân (Binary Search)

Trong nội dung này tất cả chúng ta sẽ tìm tòi về thuật toán tìm kiếm nhị phân (Binary search). Đây là thụât toán thông dụng để tìm kiếm địa điểm một phần tử trong một mảng đã sắp đặt.

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

Để bài: Cho một mục lục arrvàlt;> đã được sắp đặt gồm n phần từ , viết một hàm đề ra địa điểm của phần từ x trong mảng.


Một cách tìm kiếm dễ dàng hơn rất là nhiều này là thụât toán tìm kiếm tuần tự (linear search) nhưng độ cầu kỳ khá lớn lên tới O(n), không khả thi để thực hiện tìm kiếm trên một mảng lớn. Để khắc phục bài toán này tất cả chúng ta sẽ sử dụng thụât toán tìm kiếm nhị phân (binary search) được giới thiệu bên dưới.

1. Tìm kiếm nhị phân (Binary Search)

Một cách tìm kiếm dễ dàng hơn rất là nhiều này là thụât toán tìm kiếm tuần tự (linear search) nhưng độ cầu kỳ khá lớn lên tới O(n), không khả thi để thực hiện tìm kiếm trên một mảng lớn. Để khắc phục bài toán này tất cả chúng ta sẽ sử dụng thụât toán tìm kiếm nhị phân (binary search) được giới thiệu bên dưới.

Thụât toán tìm kiếm nhị phân (Binary Search) hay còn gọi là tìm kiếm một nửa là thụât toán tiếp kiếm được sử dụng rất là nhiều trong thực tiễn cho phép tìm kiếm địa điểm của một phần tử trong một mảng đã được sắp đặt.

Thụât toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp đặt bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Khởi đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm bé hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng & nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm ra hoặc đã duyệt hết.

Xem Thêm  Break trong C và cách thoát khỏi vòng lặp

Tham khảo thêm: Cond Là Gì – Cond Vnds, Deadstock Là Gì

Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn đối với tìm kiếm tuyết tính ở các mảng có độ dài lớn & đã được sắp đặt. Trái lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ & chưa được sắp đặt.

2. Sáng tạo triển khai thụât toán

Thuật toán tìm kiếm nhi phân là một thuật toán khá phổ biến & chỉ dùng được với một mảng đã sắp đặt. Để triển khai thuật toán này hãy chắc cú rằng mảng đã được sắp đặt. Sau đây là sáng kiến triển khai thuật toán.

Xét một đoạn trong mảng arr. Bây giờ giá trị của left & right lần luợt là 0 & số phần tử của mảng – 1.So sánh x với phần tử nằm ở địa điểm trung tâm của mảng (mid = (left + right) /2). Nếu x bằng arr thì trả về địa điểm & thoát vòng lặp.Nếu x x sẽ nằm ở phía bên trái tức là từ arr.Nếu x > arr thì chắc cú x sẽ nằm ở phía bên phải mid tức là ở khoảng arr.Tiếp tục thực hiện chia đôi các khoảng tìm kiếm tới bao giờ tìm ra được địa điểm của x trong mảng hoặc khi đã duyệt hết mảng.

Người ta đã minh chứng được độ phực tạp của thụât toán tìm kiếm nhi phân trong trường hợp tốt đặc biệt là O(1), trong trường hợp xấu đặc biệt là O(log2n) & bình quân cũng là O(log2n). Không những thế, ta không nên quên rằng trước khi sử dụng tìm kiếm nhị phân, dãy khoá phải được sắp đặt rồi, tức là thời gian ngân sách cho việc sắp đặt cũng cần phải tính đến.

Xem Thêm  dfn

Tham khảo thêm: Decision Maker Là Gì ? Decision Maker Là Gì, Nghĩa Của Từ Decision Maker

3. Triển khai thụât toán

Sau đây là các bước triển khai thuật toán, các bước làm đều được bình luận ở từng đoạn.

#include using namespace std;//Hàm tìm kiếm nhi phânint binarySearch(int arrvàlt;>, int left, int right, int x) { int middle; while(left arr) left = middle + 1; else //Trái lại right = middle – 1; } //Trả về -1 nếu như không tìm ra gía trị trong mảng. return -1;}int main() { int arrvàlt;> = {15, 20, 25, 30, 31, 44, 66}; //Lấy ra độ dài của mảng int n = sizeof(arr) / sizeof(arrvàlt;0vàgt;); //Phần từ cần tìm int x = 25; // n -1 là địa điểm cuối cùng trong mảng. int result = binarySearch(arr, 0, n-1, x); cout
Trên đây là phần giới thiệu cũng như triển khai của thụât toán tìm kiếm nhị phân. Đây cũng là một thuật toán thường được sử dụng cũng như rât hữu dụng trong công cuộc giải các bài toán tìm kiếm. Rất mong nội dung sẽ hữu dụng cho bạn !

Tiếp thị

Bài trước Bài tiếp

Tìm các số chẵn lẻ bằng Queue & Stack

Để làm được bài này các bạn phải có học thức về kết cấu Queue…

Setup hàng đợi Queue bằng mảng 1 chiều

Tất cả chúng ta sẽ cùng với nhau tìm tòi về cách thiết lập hàng đợi Queue bằng…

Setup hàng đợi Queue bằng mục lục link

Tất cả chúng ta sẽ cùng với nhau tìm tòi về cách khởi tạo kết cấu dữ liệu…

Hàng đợi Queue là gì? Kết cấu dữ liệu & các cách thiết lập Queue

Trong chỉ dẫn này mình sẽ giới thiệu các bạn một kết cấu lưu trữ…

Bài tập kiểm soát số nguyên tố bằng Stack

Tất cả chúng ta sẽ cùng với nhau tạo một kết cấu Stack với mục lục link…

Bài tập chuyển hóa cơ số bằng Stack

Xem Thêm  x2

Trong chỉ dẫn này mình sẽ thực hiện giải một bài toán chuyển hóa cơ…

Setup Stack bằng mảng 1 chiều

Tất cả chúng ta sẽ lần lượt thực hiện tạo các hàm căn bản cho Stack như:…

Setup Stack bằng mục lục link

Tất cả chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Kết cấu & phương châm hoạt động ra sao?

Trong chỉ dẫn này mình sẽ giới thiệu các bạn một kết cấu lưu trữ…

Cây đỏ đen là gì? Kết cấu của Red-Black Tree

Trong chỉ dẫn này mình sẽ giới thiệu các bạn một kết cấu dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Tất cả chúng ta sẽ cùng với nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX & MIN trong cây nhị phân tìm kiếm

Tất cả chúng ta sẽ thực hiện 1 vài cách tìm thấy giá trị MAX & MIN…

Xuất Node con & lá trong cây nhị phân tìm kiếm

Trong chỉ dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong chỉ dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Thêm Node vào cây nhị phân tìm kiếm

Trong chỉ dẫn này mình sẽ giới thiệu các bạn về kết cấu dữ liệu…

Kết cấu cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các kết cấu dữ…

Gộp hai mục lục link đôi

Tất cả chúng ta sẽ cùng với nhau tìm tòi về cách nối hai mục lục link…

Xét một đoạn trong mảng. Bây giờ giá trị của left & right lần luợt là 0 & số phần tử của mảng – 1.So sánh x với phần tử nằm ở địa điểm trung tâm của mảng. Nếu x bằng arr

Viết một bình luận