Cấu trúc dữ liệu và giải thuật: Giải thuật tìm kiếm nhị phân (Binary search)

#1

Giải thuật tìm kiếm nhị phân (Binary search)

Thuật toán này áp dụng cho các dãy phần tử đã có trật tự (tăng hoặc giảm). Phần tử cần tìm gọi là khóa tìm kiếm. Tập các số nguyên được biểu diễn bằng mảng 1 chiều (dãy).
Sử dụng nguyên lý nổi tiếng của “Lý thuyết thông tin” (Information Theory):

Khi xử lý bất cứ công việc gì, nếu ta biết cách làm giảm độ bất định đi một nửa thì tự khắc ta sẽ tăng được sự xác định lên gấp đôi.

1. Ý tưởng thuật toán

Các phần tử trong dãy có quan hệ tuyến tính a[i-1] < a[i] < a[i+1] (ví dụ trật tự tăng). Xác định khóa x có trong dãy không.

  • Nếu x < a[i]: x chỉ có thể tồn tại trong đoạn [a[0], a[i - 1]].
  • Nếu x > a[i]: x chỉ có thể tồn tại trong đoạn [a[i + 1], a[n - 1]].

Áp dụng luật “Giảm độ bất định lớn nhất” của “Lý thuyết thông tin”, ta thường chọn phần tử mốc ở giữa hoặc gần giữa của dãy. Mỗi bước ta so sánh x với phần tử này 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 ở nửa trước hay nửa sau của dãy. Quy trình tiếp diễn tới khi đoạn con cuối cùng suy biến thành điểm giữa.

  • Nếu x ≡ a[mid] (x trùng với phần tử giữa): Tìm thấy khóa x.
  • Nếu x ≠ a[mid]: Không tìm thấy khóa x.

2. Các bước của thuật toán

Bước 1: int mid, left = 0, right = n - 1 //mid: phần tử giữa, left: phần tử đầu, right: phần tử cuối
Bước 2: Khi chưa xét hết dãy (left <= right) thì lặp lại các bước sau:
- Bước 2.1. Tính điểm giữa mid = (left + right) / 2.
- Bước 2.2. So sánh khóa x với phần tử tại vị trí mid

  • Nếu x < a[mid] thì right = mid - 1;
  • Nếu x > a[mid] thì left = mid + 1;
  • Nếu x = a[mid] (tìm thấy x) --> kết thúc.
  • Nếu x ≠ a[mid] (không tìm thấy x) --> kết thúc.

3. Cài đặt (C++)

int binarySearch(int a[], int n, int x) {
    int mid, left = 0, right = n - 1, k = -1;
    while (left <= right) {
        mid = (left + right) / 2;
        if(x > a[mid]) left = mid + 1;
        else if(x < a[mid]) right = mid - 1;
        else {
            k = mid;
            break;
        }
    }
    return k;
}

4. Độ phức tạp của thuật toán

  • Tốt nhất:
    Số lần so sánh: 1 (Phần tử giữa dãy có giá trị bằng khóa x).

  • Xấu nhất:
    Số lần so sánh: log2(n) (Duyệt hết dãy mới tìm thấy x hoặc không tìm thấy x).

  • Trung bình:
    Số lần so sánh: log2(n/2) (Giả sử mọi phần tử trong dãy đều có xác suất như nhau).

Độ phức tạp của thuật toán tìm kiếm này là O(log2(n)) < O(n) của thuật toán tìm tuần tự (Sequential search), vì vậy nếu cùng cỡ dữ liệu đầu vào n thì thuật toán này chạy nhanh hơn.

2 Likes
#2 
#include <iostream>
using namespace std;

int binarySearch(int a[], int n, int x) {
    int mid, left = 0, right = n - 1;
    do {
        mid = (left + right) / 2;
        if(x == a[mid]) return mid;
        else
            if(x > a[mid]) left = mid + 1;
            else right = mid - 1;
    } while(left <= right);
    return -1;
}

int main() {
	int a[0];
	int n = 0;
	int x = 32765;
	
	int found = binarySearch(a, n, x);
	if (found == -1)
		cout << "not found" << endl;
	else
		cout << a[found] << endl;
	
	return 0;
}

Có bug :smiley:

Success #stdin #stdout 0.01s 5528KB

   32765
2 Likes
#3

Mình copy, paste nguyên code thấy vẫn đúng mà nhỉ.

not found

#4 
mid = (left + right) / 2;
if(x == a[mid]) return mid;

Trong trường hợp mảng không có phần tử nào thì code này vẫn cố truy cập vào a[0] 1 lần ấy bạn. Trường hợp này nên fix như thế nào nhỉ :smiley:

3 Likes
#5

à à mình hiểu ý bạn rồi, vậy thì mình đưa điều kiện lên trước, để nếu n = 0 thì left = 0 và right = -1, như vậy nó sẽ bỏ qua luôn nhỉ :sweat_smile:

int binarySearch(int a[], int n, int x) {
    int mid, left = 0, right = n - 1, k = -1;
    while (left <= right) {
        mid = (left + right) / 2;
        if(x > a[mid]) left = mid + 1;
        else if(x < a[mid]) right = mid - 1;
        else {
            k = mid;
            break;
        }
    }
    return k;
}
3 Likes
#6

Vậy mình xin phép sửa lại code cho bài viết. :smile: :smile: :smile:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?