SẮP XẾP & TÌM KIẾM
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Thụât toán tìm kiếm nhị phân (Binary Search)

Trong bài viết này chúng ta sẽ tìm hiểu về thuật toán tìm kiếm nhị phân (Binary search). Đây là thụât toán phổ biến để tìm kiếm vị trí một phần tử trong một mảng đã sắp xếp.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Để bài: Cho một danh sách arr[] đã được sắp xếp gồm n phần từ , viết một hàm đưa ra vị trí của phần từ x trong mảng.

Ví dụ:

Input : arr[] = {15, 20, 25, 30, 31, 44, 66}
        x = 25;
Output : 2

Một cách tìm kiếm đơn giản hơn rất nhiều đó là thụât toán tìm kiếm tuần tự (linear search) nhưng độ phức tạp 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. Để giải quyết bài toán này 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.

Bài viết này được đăng tại [free tuts .net]

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

Thụât toán tìm kiếm nhị phân (Binary Search) hay còn được 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 nhiều trong thực tế cho phép tìm kiếm vị trí của một phần tử trong một mảng đã được sắp xếp.

thuat toan tim kiem tuyen tinh gif

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 xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầ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 nhỏ 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 và 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 thấy hoặc đã duyệt hết.

Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược 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ỏ và chưa được sắp xếp.

2. Ý tưởng 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á thông dụng và chỉ dùng được với một mảng đã sắp xếp. Để triển khai thuật toán này hãy chắc chắn rằng mảng đã được sắp xếp. Sau đây là ý tưởng triển khai thuật toán.

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

Người ta đã chứng minh đượ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 nhất là O(1), trong trường hợp xấu nhất là O(log2n) và trung bình cũng là O(log2n). Tuy nhiên, 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 xếp rồi, tức là thời gian chi phí cho việc sắp xếp cũng phải tính đến.

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 thực hiện đều được comment ở từng đoạn.

#include <bits/stdc++.h>
using namespace std;

//Hàm tìm kiếm nhi phân
int binarySearch(int arr[], int left, int right, int x) {
    int middle;

    while(left <= right) {
        // Lấy vị trí ở giữa left và right
        middle = (left + right) / 2;

        // Nếu phần từ ở giữa bằng x thì trả về
        // vị trí
        if (arr[middle] == x)
            return middle;

        // Nếu x lớn hơn phần tử ở giữa thì
        // chắc chắn nó nằm bên phải.
        // Chỉ định left phần từ ở giữa + 1
        if (x > arr[middle])
            left = middle + 1;
        else
            //Ngược lại
            right = middle - 1;
    }

    //Trả về -1 nếu không tìm thấy gía trị trong mảng.
    return -1;
}
int main() {
    int arr[] = {15, 20, 25, 30, 31, 44, 66};

    //Lấy ra độ dài của mảng
    int n = sizeof(arr) / sizeof(arr[0]);
    //Phần từ cần tìm
    int x = 25;
    
    // n -1 là vị trí cuối cùng trong mảng.
    int result = binarySearch(arr, 0, n-1, x);

    cout << result;
}

Khởi chạy chươn trình chúng ta sẽ nhận được kết quả là vị trí của 25 trong mảng.

Output : 2

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 hay được sử dụng cũng như rât hữu ích trong quá trình giải các bài toán tìm kiếm. Rất mong bài viết sẽ hữu ích cho bạn !

Cùng chuyên mục:

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

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

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

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

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

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

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

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

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

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ì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

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

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

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

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

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

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

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

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

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

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

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

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

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

Trong hướng 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

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

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

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

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

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

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

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

Cấu trúc 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 cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top