Tìm kiếm nhị phân

Tìm kiếm trong mảng với độ phức tạp thời gian O(n) đã tốt, nhưng có thể tối ưu hơn nữa xuống O(log n) bằng một phương pháp gọi là tìm kiếm nhị phân (Binary search). 

Điều kiện để dùng tìm kiếm nhị phân: Các phần tử của mảng phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần.

Ví dụ, 

int Arr[]={1,2,3,4,5};
int Brr[]={5,3,9,6,7};

Với Arr, ta có thể dùng tìm kiếm nhị phân để tìm một phần tử vì tất cả phần tử của Arr được sắp xếp theo thứ tự tăng dần.

Ta không thể dùng tìm kiếm nhị phân trên Brr vì các phần tử của Brr không theo thứ tự.

Logic cơ bản

Kiểm tra chính giữa mảng, 

1. Nếu phần tử đó bằng giá trị cần tìm thì in ra phần tử đó,
2.  nếu phần tử đó nhỏ hơn khóa cần tìm thì tìm ở bên phải của phần mảng còn lại, 
3.  nếu phần tử đó lớn hơn thì tìm ở bên trái của phần mảng còn lại.

Lặp lại quy trình cho đến khi tìm thấy khóa cần tìm, nếu không thì trả về -1.

Quy trình chi tiết

1. Đầu tiên, ta khởi tạo 2 biến trỏ đến đầu và cuối mảng. Sau đó dùng vòng lặp while với điều kiện vị trí đầu luôn nhỏ hơn hoặc bằng vị trí cuối.

    int s=0; //bắt đầu
    int e=n; //kết thúc
    
    while(s<=e){
    
    }

2. Tìm phần tử ở giữa bằng cách tính (s+e)/2. Nếu mid bằng chính xác với khóa cần tìm thì trả về mid.

    int s=0; //Bắt đầu
    int e=n; //Kết thúc
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Vị trí giữa của mảng

        if(arr[mid]==key){   //Nếu bằng key thì trả về chỉ số
            return mid;
        }
    
    }

3. Nếu phần tử ở giữa lớn hơn khóa cần tìm, điều đó có nghĩa là khóa cần tìm phải nằm ở phía bên trái của mảng. Vì vậy, ta chuyển vị trí cuối của mảng đến mid-1. Lúc này, ta chỉ còn mảng có kích thước n/2 và lặp lại quy trình trên.

    int s=0; //Bắt đầu
    int e=n; //Kết thúc
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Vị trí giữa mảng

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;         //Chuyển vị trí kết thúc sang mid-1
        }
    
    }

4. Nếu không có điều kiện nào trong số này đúng thì phần tử cần tìm phải lớn hơn phần tử ở giữa. Vì vậy, ta tìm ở phần bên phải của mảng và chuyển vị trí đầu của mảng đến mid+1.

    int s=0;
    int e=n;
    while(s<=e){
        int mid=(s+e)/2;

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;
        }
        else{
            s=mid+1;   //Chuyển vị trí bắt đầu sang mid+1
        }
    }

Ta chạy chương trình cho đến khi tìm thấy phần tử. Nếu không tìm thấy phần tử thì trả về -1.

Độ phức tạp thời gian

Ở mỗi bước, số phần tử giảm còn một nửa. Điều đó có nghĩa là thời gian thực hiện ở mỗi bước bằng một nửa bước trước đó. Thời gian giảm theo cấp số logarit, vì vậy độ phức tạp thời gian của tìm kiếm nhị phân là O(log n).