1. Thuật toán tìm kiếm nhị phân là gì?

Thuật toán tìm kiếm nhị phân hay còn gọi là tìm kiếm nửa khoảng là thuật toán tìm kiếm một phần tử có trong một danh sách (hoặc) mảng đã được sắp xếp. Ý tưởng của thuật toán tìm kiếm nhị phân là tại mỗi bước ta so sánh giá trị x cần tìm với phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở bên trái hay nửa bên phải của dãy tìm kiếm hiện hành.

Giả xử ta xét mảng A[n] có thứ tự tăng, khi ấy ta có A[i-1] < A[i] < A[i+1]

• So sánh nếu x > A[i] thì x chỉ có thể xuất hiện trong đoạn từ A[i +1] đến A[n -1] ( Giá trị x lúc này chỉ có thể thuộc nửa bên phải của phần tử nằm giữa mảng là A[i] )
• So sánh nếu x < A[i] thì x chỉ có thể xuất hiện trong đoạn tử A[0] đến A[i] ( Giá trị x lúc này chỉ có thể thuộc nửa bên trái của phần tử nằm giữa mảng là A[i] )
• Tiếp tục lặp lại việc tìm kiếm bên nửa bên trái hoặc nửa bên phải của mảng cho đến khi tìm thấy phần tử cần tìm là phần tử nằm giữa ở mảng được giới hạn

Các bước trong thuật toán tìm kiếm nhị phân (Binary Search)

Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong khoảng từ A[left] đến A[right], các bước của giải thuật tìm kiếm nhị phân thực hiện như sau:

Bước 1: Gán các các giá trị left=0; right=N-1;
Bước 2:
    Lấy ra chỉ số phần tử giữa dãy hiện hành: mid=(left+right)/2; 
    So sánh giá trị A[mid] với giá trị x cần tìm. Có 3 trường hợp sảy ra:
        Nếu A[mid] = x; thì tìm thấy phần tử có giá trị x tại vị trí mid. Dừng việc tìm kiếm
        Nếu A[mid] > x; thì thực hiện gán right = mid - 1;
        Nếu A[mid] < x; thì thực hiện gán left = mid + 1;
Bước 3: Nếu vòng lặp vẫn thỏa mãn điều kiện left <= right; // nghĩa là vẫn còn phần tử trong dãy hiện hành
    Lặp lại Bước 2
    Ngược lại : Dừng việc tìm kiếm

Minh họa thuật toán tìm kiếm nhị phân trong một dãy (hay mảng) đã được sắp xếp theo thứ tự

Trong ví dụ dưới đây, chúng ta sẽ có sẵn một dãy ban đầu đã được sắp xếp theo chiều tăng dần, các phần tử trong dãy này sẽ là [2,4,5,7,8,9,12,14,17,19,22,25,27,28,33,37] chúng ta cần tìm x = 22 trong dãy sẽ thực hiện như sau:

Giải thích tìm kiếm x = 22 trong dãy trên:

• Ban đầu left = 0, right = 15
• (1) Vì 22 > 14 nên việc tìm kiếm sẽ chuyển sang nửa bên phải dãy hiện hành với: left = 8, mid = 11, right = 15
• (2) Tiếp tục, vì 22 < 25 nên sẽ tìm kiếm nửa bên trái dãy hiện hành với: left = 8, mid = 9, right = 10
• (3) Cuối cùng, vì 22 > 19 nên việc tìm kiếm chuyển sang nửa bên phải dãy hiện hành, lúc này ta tìm thấy phần tử 22 tại vị trí left = mid = right = 10

2. Minh họa thuật toán tìm kiếm nhị phân trong C

Việc cài đặt thuật toán tìm kiếm nhị phân trong ngôn ngữ C được thường được triển khai cài đặt thông qua vòng lặp while, dựa vào ý tưởng của các bước bên trên chúng ta hoàn toàn có thể xây dựng một hàm tìm kiếm nhị phân binary_search(int A[], int n, int x) – hàm này gồm 3 tham số:

• int A[] là mảng chứa các phần tử
• int n là số lượng phần tử có trong mảng int A[]
• int x là phần tử cần tìm trong int A[]

Hàm binary_search(int A[], int n, int x) được xây dựng như sau:

int binary_search(int A[],int n,int x){
    //Khai bao cac bien vi tri
    int left, right, mid; 
    //Gan left ban dau bang 0, right ban dau bang n - 1 (vi tri cuoi cung)
    left=0; right=n-1;
    //Thuc hien vong lap do
    do{
        //Lay ra vi tri phan tu giua trong day hien hanh
        mid=(left+right)/2;
        //Neu phan tu giua day bang x thi viec tim kiem thanh cong
        if(A[mid] == x){
            return mid; //Tra ve vi tri cua phan tu tim thay
        }
        else if(A[mid] < x){//Nguoc lai, neu phan tu giua nho hon x
            //Thay doi lai bien left = mid + 1 de tiep tuc tim kiem nua ben phai cua day moi
            left = mid + 1;
        }else{//Nguoc lai, neu phan tu giua khong nho hon x
            //Thay doi lai bien right = mid - 1 de tiep tuc tim kiem nua ben trai cua day moi
            right = mid - 1;
        }
    }while(left<=right);//Dieu kien lap khi left < right
    //Truong hop khong tim thay phan tu co gia tri bang x sau khi duyet het mang se tra ve -1
    return -1;
}

Lưu ý:

• Nếu tìm thấy phần tử thì vị trí mid của dãy hiện hành sẽ luôn có giá trị A[mid] = x vì thế nên, ta có thể trả về vị trí tìm thấy phần tử là return mid cho hàm binary_search().
• Trong trường hợp duyệt qua toàn bộ mảng mà hàm vẫn chưa gọi câu lệnh return mid; thì điều này nghĩa là không có phần tử có giá trị x trong mảng. Khi đó ta sẽ return -1 bên ngoài vòng lặp để trả về giá trị -1 cho hàm binary_search() để báo hiệu việc không tìm thấy phần tử.

Chương trình đầy đủ về thuật toán tìm kiếm nhị phân với mảng các số nguyên trong ngôn ngữ C như sau:

#include <stdio.h>
//Khai bao ham tim kiem nhi phan
int binary_search(int A[],int n,int x){
    //Khai bao cac bien vi tri
    int left, right, mid; 
    //Gan left ban dau bang 0, right ban dau bang n - 1 (vi tri cuoi cung)
    left=0; right=n-1;
    //Thuc hien vong lap do while
    do{
        //Lay ra vi tri phan tu giua trong day hien hanh
        mid=(left+right)/2;
        //Neu phan tu giua day bang x thi viec tim kiem thanh cong
        if(A[mid] == x){
            return mid; //Tra ve vi tri cua phan tu tim thay
        }
        else if(A[mid] < x){//Nguoc lai, neu phan tu giua nho hon x
            //Thay doi lai bien left = mid + 1 de tiep tuc tim kiem nua ben phai cua day moi
            left = mid + 1;
        }else{//Nguoc lai, neu phan tu giua khong nho hon x
            //Thay doi lai bien right = mid - 1 de tiep tuc tim kiem nua ben trai cua day moi
            right = mid - 1;
        }
    }while(left<=right);//Dieu kien lap khi left < right
    //Truong hop khong tim thay phan tu co gia tri bang x sau khi duyet het mang se tra ve -1
    return -1;
}

int main(){
    //Khai bao bien n lam so luong phan tu mang
    int n = 16;
    //Khai bao mang gom cac phan tu
    int A[n] = {2,4,5,7,8,9,12,14,17,19,22,25,27,28,33,37};
    //Khai bao gia tri can tim trong mang A
    int x = 22;
    //Khai bao bien index de nhan ket qua tim kiem duoc tra ve tu ham binary_search(A,n,x)
    int index = binary_search(A,n,x);
    //Neu ket qua index bang -1
    if(index == -1){
    printf("Khong tim thay phan tu x = %d", x);
    }else{ //Nguoc lai, neu index khong bang -1
    printf("Tim thay x = %d tai vi tri %d", x, index);
    }
}

Kết quả:

Giải thích:

• Đầu vào: A[] = {2,4,5,7,8,9,12,14,17,19,22,25,27,28,33,37}, n = 16, x = 22;
• Đầu ra: 10
• Kết quả: Phần tử x tồn tại ở chỉ số 10 của mảng A

Các bạn có thể áp dụng việc nhập xuất các phần tử vào trong mảng A[] và nhập giá trị x cần tìm , sau đó mới thực hiện gọi hàm binary_search(A,n,x) để phục vụ cho việc tìm kiếm phần tử cho chính bài toán của mình. Trong bài này, mảng A[] được cố định bằng: {2,4,5,7,8,9,12,14,17,19,22,25,27,28,33,37}, số lượng phần tử n = 16 và phần tử cần tìm x = 22.

3. Đánh giá thuật toán tìm kiếm nhị phân