close

Giải thuật Tìm kiếm nhị phân (Binary Search) trong C++ - Giải thích, Ví dụ và Mã nguồ

Giải thuật tìm kiếm nhị phân là một cách hiệu quả hơn để tìm kiếm một phần tử cụ thể trong một danh sách đã được sắp xếp. Khác với tìm kiếm tuyến tính, kiểm tra các phần tử tuần tự, tìm kiếm nhị phân chia danh sách thành các nửa và so sánh phần tử mục tiêu với phần tử ở giữa. Quá trình này lặp lại cho đến khi tìm thấy phần tử cần tìm hoặc phạm vi tìm kiếm trở thành trống.

Cách hoạt động

  1. Bắt đầu với toàn bộ danh sách đã sắp xếp.
  2. Tìm phần tử ở giữa của phạm vi tìm kiếm hiện tại.
  3. So sánh phần tử ở giữa với giá trị mục tiêu.
  4. Nếu phần tử ở giữa bằng giá trị mục tiêu, tìm kiếm thành công.
  5. Nếu phần tử ở giữa lớn hơn giá trị mục tiêu, tìm kiếm ở nửa trái của phạm vi.
  6. Nếu phần tử ở giữa nhỏ hơn giá trị mục tiêu, tìm kiếm ở nửa phải của phạm vi.
  7. Lặp lại các bước 2-6 cho đến khi tìm thấy phần tử cần tìm hoặc phạm vi tìm kiếm trở thành trống.

Ví dụ

Hãy xem xét một danh sách đã được sắp xếp của các số nguyên và muốn tìm số 34 bằng cách sử dụng tìm kiếm nhị phân.

Danh sách đã sắp xếp: {12, 23, 34, 45, 56, 67, 89, 90}

  1. Bắt đầu với toàn bộ danh sách.
  2. Phần tử ở giữa: 56 (vị trí 4). So sánh với 34.
  3. 56 lớn hơn 34. Tìm kiếm ở nửa trái.
  4. Phần tử ở giữa mới: 23 (vị trí 1). So sánh với 34.
  5. 23 nhỏ hơn 34. Tìm kiếm ở nửa phải.
  6. Phần tử ở giữa mới: 45 (vị trí 3). So sánh với 34.
  7. 45 lớn hơn 34. Tìm kiếm ở nửa trái.
  8. Phần tử ở giữa mới: 34 (vị trí 2). Tìm thấy mục tiêu.

Mã ví dụ trong C++

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};
    int target = 34;

    int result = binarySearch(numbers, target);

    if (result != -1) {
        std::cout << "Phần tử " << target << " được tìm thấy tại vị trí " << result << std::endl;
    } else {
        std::cout << "Phần tử " << target << " không được tìm thấy trong danh sách" << std::endl;
    }

    return 0;
}

Trong ví dụ trên, chúng ta sử dụng hàm binarySearch để tìm số 34 trong danh sách đã được sắp xếp của các số nguyên. Kết quả sẽ là vị trí của số 34 trong danh sách (vị trí bắt đầu từ 0) hoặc -1 nếu số không được tìm thấy.