Thuật toán tìm kiếm nhị phân

Bài toán: Cho một mảng đã sắp xếp arr [] gồm n phần tử, hãy viết hàm tìm kiếm một phần tử x cho trước trong arr [].

Phương pháp tiếp cận tìm kiếm tuyến tính : Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính. Độ phức tạp về thời gian của tìm kiếm Tuyến tính là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.

Phương pháp tiếp cận tìm kiếm nhị phân: Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng trong một mảng được sắp xếp bằng cách chia đôi khoảng thời gian tìm kiếm nhiều lần. Ý tưởng của tìm kiếm nhị phân là sử dụng thông tin mà mảng được sắp xếp và giảm độ phức tạp về thời gian thành O (Log n). Các bước cơ bản để thực hiện Tìm kiếm nhị phân là:

• Bắt đầu với một khoảng bao gồm toàn bộ mảng. 
• Nếu giá trị của khóa tìm kiếm nhỏ hơn mục ở giữa khoảng, hãy thu hẹp khoảng đó xuống nửa dưới. 
• Nếu không, hãy thu hẹp nó xuống nửa trên. 
• Lặp lại kiểm tra cho đến khi giá trị được tìm thấy.

Thí dụ:

Thuật toán tìm kiếm nhị phân: Về cơ bản, chúng ta bỏ qua một nửa số phần tử chỉ sau một lần so sánh.

1. So sánh x với phần tử ở giữa.
2. Nếu x khớp với phần tử ở giữa, chúng ta trả về chỉ số giữa.
3. Khác Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa mảng con bên phải sau phần tử giữa. Vì vậy, chúng tôi tái diễn cho một nửa bên phải.
4. Khác (x nhỏ hơn) lặp lại cho nửa bên trái.

Code tham khảo: 

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
  
int main() {
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1)
        ? cout << "Phần tử không có trong mảng"
        : cout << "Phần tử tìm thấy tại vị trí thứ " << result;
    return 0;
}

Sử dụng cấu trúc lặp trong tìm kiếm nhị phân

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}
  
int main() {
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1)
        ? cout << "Phần tử không có trong mảng"
        : cout << "Phần tử tìm thấy tại vị trí thứ " << result;
    return 0;
}