THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

     

Thuật toán kiếm tìm kiếm nhị phân Binary tìm kiếm C++. Cách setup thuật toán, ưu nhược điểm, độ phức tạp. đối chiếu tìm kiếm nhị phân với tìm kiếm tuần tự. Thuộc mình mày mò tất cả trong bài viết này nhé.

Bạn đang xem: Thuật toán tìm kiếm nhị phân


1. Thuật toán tra cứu kiếm

Trong lập trình bạn sẽ thường xuyên gặp phải câu hỏi tìm kiếm. Tra cứu kiếm hiểu theo đúng nghĩa black của nó là chúng ta đi search một đồ vật gì đó. Toàn bộ các bề ngoài tìm kiếm như tra google, tra cứu trên website, ứng dụng, tra cứu vớt tên . . . đều áp dụng thuật toán tra cứu kiếm.

Trong lập trình search kiếm dùng để làm tìm vị trí, tróc nã vấn bộ phận cần search trong dữ liệu xử lý trường đoản cú đó tiến hành các thao tác cần thiết. Vày nó được sử dụng rất nhiều nên đó là một trong những các thuật toán cực kỳ quan trọng cùng với mỗi xây dựng viên.

Xem thêm: Tác Giả Bài Thơ Hà Nội 36 Phố Phường, Hà Nội 36 Phố Phường

Bạn sẽ thuận lợi nghe thấy 5 dạng thuật toán kiếm tìm kiếm thịnh hành nhất kia là:

Tìm kiếm đường tính – Sequential search hay có cách gọi khác là Linear searchTìm tìm nhị phân – Binary searchThuật toán Ternary SearchThuật toán Jump SearchThuật toán Exponential Search

Hai thuật toán bản thân liệt kê đầu hay được nhắc tới nhiều các hơn. Trong các số đó thuật toán kiếm tìm kiếm con đường tính là thuật toán đơn giản nhất với được sử dụng nhiều nhất bởi vì nó dễ dàng và thực sự dễ dàng hình dung. Mặc dù tốc độ, sự về tối ưu của chính nó thuộc vào loại thấp nhất, đấy là lý do bạn nên trang bị thêm một vài thuật toán search kiếm khác.

Bài toán tìm kiếm trong bài viết này bản thân nêu ra như sau: cho mảng arr<> đã sắp xếp có n phần tử, viết hàm tìm kiếm trả về chỉ số của phần tử có giá trị x trong arr<>. (tìm địa điểm của x vào mảng)

2. Thuật toán tìm kiếm nhị phân – Binary search

Thuật toán tra cứu kiếm nhị phân (Binary search) hay nói một cách khác là thuật toán tìm kiếm phân chia đôi, tìm kiếm nửa khoảng, binary chop là thuật toán bao gồm ứng dụng tính chất chia để trị. Ta sẽ tiến hành chia song mảng ban đầu, nếu thành phần ở giữa to hơn, hoặc nhỏ dại hơn phần tử cần tìm kiếm ta đang thu hẹp miền cần tìm tới hai đầu tương ứng. Thường xuyên làm như vậy tính đến khi hết mảng hoặc đưa ra vị trí bộ phận cần tìm.

Xem thêm: Đề Xuất 4/2022 # Viết Đoạn Văn Về Món Ăn Yêu Thích Bằng Tiếng Anh # Top Like


*

Ý tưởng thuật toán tìm kiếm kiếm nhị phân:

Chia mảng ban đầu thành 2 phần, lấy mid làm bộ phận giữa: mid = (left + high) /2;Nếu arr == x thì trả về vị trí của midNếu x ví như x > arr bây giờ x sẻ sinh sống bên đề xuất mid. Đệ quy thuật toán tìm xở mảng bên phảiNếu không có bộ phận thỏa mãn ta trả về -1

Cài đặt thuật toán bằng C/C++:

int binary_Search(int arr<>, int low, int high, int x) if (high >= low) // trong những lúc chưa xét hết int mid = low + (high - low) / 2; // tương tự mid = (low + high)/2; if (arr == x) // Nếu bộ phận mid bằng phần tử tìm kiếm thì ngừng return mid; if (arr > x) // trường hợp x nhỏ tuổi hơn mid, đệ quy tìm phía bên trái return binary_Search(arr, low, mid - 1, x); return binary_Search(arr, mid + 1, high, x); // nếu x > mid ta đệ quy tra cứu kiếm nửa bên cần return -1; // Nếu không kiếm thấy ta trả về -1; Đánh giá bán thuật toán kiếm tìm kiếm nhị phân:

Độ phức tạp trung bình: O (logn)Độ phức tạp giỏi nhất: O(1)Độ tinh vi không gian: O(1)

3. đối chiếu tìm tìm nhị phân với tìm kiếm kiếm tuyến tính

Khác với tìm kiếm đường tính – Linear sort sẽ thực hiện vòng lặp duyệt từ trên đầu mảng lần lượt về phía cuối mảng cho tới khi tìm được thành phần cần kiếm tìm thì đã dừng lại. Để dễ hiểu, chúng ta xem hình minh họa so sánh Binary tìm kiếm với Sequential phía dưới.


*
So sánh tìm kiếm kiếm nhị phân cùng tìm kiếm tuyến tính

Một số ưu điểm yếu giữa nhì thuật toán với nhau:

Tìm tìm nhị phân chỉ vận động trên mảng đã sắp xếp có sản phẩm công nghệ tựTìm kiếm nhị phân phù hợp với mảng bao gồm độ lâu năm lớnThuật toán tìm kiếm kiếm nhị phân bao gồm hiệu xuất giỏi hơnTìm kiếm tuần tự phù hợp với mảng nhỏ tuổi và không sắp xếp.. . .

Ngoài ra còn có tương đối nhiều ưu nhược điểm khác nữa

Lời kết: Cảm ơn bạn đã đọc tới các dòng cuối cùng trên bài viết của mình. Trường hợp có thắc mắc gì chớ ngại nhằm lại comment xuống phía dưới bài viết nhé! Chúc bạn thành công!