C/C++

Binary Search trong C++: Cách tìm kiếm hiệu quả trong mảng đã sắp xếp

Posted on by Dục Đoàn Trình
Rate this post

Binary Search (tìm kiếm nhị phân) là một thuật toán tìm kiếm mảng đã sắp xếp. Nó sử dụng phương pháp phân chia để tìm kiếm một giá trị trong mảng.

Các bài viết liên quan:

Trong C++, có thể sử dụng hàm lower_bound() và upper_bound() trong thư viện STL (Standard Template Library) để thực hiện binary search.

Ví dụ:

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 5;
    int *result = lower_bound(arr, arr + n, x);
    if (result != arr + n)
        cout << "Tim thay x tai vi tri: " << result - arr << endl;
    else
        cout << "Khong tim thay x" << endl;
    return 0;
}

Trong ví dụ trên, mảng arr được khởi tạo với các giá trị từ 1 đến 9 và chúng ta muốn tìm x = 5. Hàm lower_bound() sẽ trả về con trỏ trỏ đến vị trí đầu tiên của giá trị x trong mảng. Nếu không tìm thấy x trong mảng, hàm sẽ trả về con trỏ trỏ đến cuối mảng.

Ngoài hàm lower_bound(), chúng ta còn có thể sử dụng hàm upper_bound() để tìm vị trí cuối cùng của giá trị x trong mảng.

Để thực hiện binary search, chúng ta có thể sử dụng vòng lặp hoặc đệ quy, tùy thuộc vào yêu cầu của bài toán.

Binary Search là thuật toán tìm kiếm hiệu quả, đặc biệt khi sử dụng với các mảng lớn vì nó chỉ duyệt qua một phần của mảng mà không cần duyệt qua toàn bộ mảng.

Giới thiệu về Binary Search trong C++

Binary Search là một thuật toán tìm kiếm hiệu quả trong một mảng đã được sắp xếp. Nó hoạt động bằng cách chia mảng thành các phần bằng nhau và so sánh giá trị tại phần tử giữa với giá trị cần tìm. Dựa vào kết quả so sánh, thuật toán sẽ tiếp tục tìm kiếm trong phần mảng bên trái hoặc bên phải của phần tử giữa.

Cấu trúc của Binary Search đảm bảo rằng số lượng phần tử cần xét bị giảm đi một nửa sau mỗi lần so sánh. Điều này giúp giảm đáng kể thời gian tìm kiếm so với việc duyệt tuyến tính qua từng phần tử.

Trong C++, thuật toán Binary Search có thể được triển khai thông qua các bước sau:

  1. Sắp xếp mảng đầu vào theo thứ tự tăng dần.
  2. Đặt giới hạn trái và giới hạn phải ban đầu cho toàn bộ mảng.
  3. Lặp cho đến khi giới hạn trái vượt quá giới hạn phải: a. Tính giá trị trung bình của giới hạn trái và giới hạn phải. b. So sánh giá trị trung bình với giá trị cần tìm kiếm:
    • Nếu giá trị trung bình lớn hơn giá trị cần tìm kiếm, giới hạn phải được đặt lại là giá trị trung bình – 1.
    • Nếu giá trị trung bình nhỏ hơn giá trị cần tìm kiếm, giới hạn trái được đặt lại là giá trị trung bình + 1.
    • Nếu giá trị trung bình bằng giá trị cần tìm kiếm, trả về vị trí đó.
  4. Nếu không tìm thấy giá trị cần tìm kiếm sau khi lặp, trả về -1 hoặc một giá trị không hợp lệ để đại diện cho việc không tìm thấy.

Binary Search trong C++ có hiệu suất cao và được sử dụng rộng rãi trong nhiều ứng dụng, đặc biệt là trong việc tìm kiếm trong mảng đã được sắp xếp.

Cách hoạt động của Binary Search

Binary Search hoạt động bằng cách tìm kiếm một giá trị cụ thể trong một mảng đã được sắp xếp. Quy trình hoạt động của Binary Search như sau:

  1. Đặt giới hạn trái và giới hạn phải ban đầu cho mảng là 0 và n-1 (với n là số lượng phần tử trong mảng).
  2. Tính giá trị trung bình của giới hạn trái và giới hạn phải: mid = (left + right) / 2.
  3. So sánh giá trị tại vị trí mid với giá trị cần tìm kiếm:
    • Nếu giá trị tại vị trí mid bằng giá trị cần tìm kiếm, trả về vị trí mid.
    • Nếu giá trị tại vị trí mid lớn hơn giá trị cần tìm kiếm, giới hạn phải được cập nhật thành mid – 1 và quay lại bước 2.
    • Nếu giá trị tại vị trí mid nhỏ hơn giá trị cần tìm kiếm, giới hạn trái được cập nhật thành mid + 1 và quay lại bước 2.
  4. Tiếp tục lặp quá trình từ bước 2 đến khi giới hạn trái vượt qua giới hạn phải.
  5. Nếu không tìm thấy giá trị cần tìm kiếm sau khi lặp, trả về giá trị không hợp lệ (ví dụ: -1) để biểu thị rằng giá trị không tồn tại trong mảng.

Quy trình này tiếp tục chia mảng thành các phần bằng nhau và chỉ tiếp tục tìm kiếm trong phần mảng thích hợp. Nhờ việc chia mảng một cách đồng đều, Binary Search có thể tìm kiếm nhanh chóng trong mảng đã được sắp xếp và có độ phức tạp thời gian logarit. Điều này làm cho nó trở thành một thuật toán tìm kiếm hiệu quả trong các tình huống mà mảng đã được sắp xếp.

Triển khai Binary Search trong C++

Dưới đây là một ví dụ khác về triển khai Binary Search trong C++:

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right)
        return -1;

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

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return binarySearch(arr, left, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, right, target);
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;

    int result = binarySearch(arr, 0, n - 1, target);

    if (result == -1)
        cout << "Khong tim thay gia tri trong mang" << endl;
    else
        cout << "Gia tri " << target << " duoc tim thay tai vi tri " << result << endl;

    return 0;
}


Trong ví dụ này, chúng ta sử dụng hàm đệ quy để triển khai Binary Search. Hàm binarySearch được gọi đệ quy với các giới hạn trái và phải cập nhật dựa trên giá trị tại vị trí giữa (mid) so với giá trị cần tìm kiếm (target). Nếu giá trị tại vị trí mid bằng target, chúng ta trả về mid. Nếu giá trị tại vị trí mid lớn hơn target, chúng ta gọi đệ quy với các phần tử bên trái của mid, ngược lại, chúng ta gọi đệ quy với các phần tử bên phải của mid. Quá trình này tiếp tục cho đến khi chúng ta tìm thấy giá trị hoặc không còn phần tử nào để xem xét.

Lưu ý rằng cả hai ví dụ trên đều giả định rằng mảng đã được sắp xếp theo thứ tự tăng dần. Nếu mảng không được sắp xếp hoặc sắp xếp theo một thứ tự khác, kết quả của Binary Search có thể không chính xác.

Phân tích độ phức tạp của Binary Search

Độ phức tạp của Binary Search được đo bằng số lần so sánh tối đa cần thực hiện để tìm kiếm một phần tử trong một mảng đã được sắp xếp.

  • Độ phức tạp thời gian của Binary Search là O(log n), trong đó n là kích thước của mảng đã được sắp xếp. Điều này có nghĩa là Binary Search hoạt động với tốc độ tăng tuyến tính khi kích thước mảng tăng lên.
  • Độ phức tạp không gian của Binary Search là O(1) vì không cần thêm bộ nhớ động để lưu trữ các phần tử khác.

Độ phức tạp O(log n) của Binary Search là kết quả của việc chia mảng thành hai nửa sau mỗi lần so sánh. Vì vậy, Binary Search rất hiệu quả khi tìm kiếm trong các mảng lớn. So với tìm kiếm tuần tự (Linear Search) có độ phức tạp O(n), Binary Search giúp tiết kiệm thời gian và tối ưu hơn đáng kể đối với việc tìm kiếm trong mảng đã được sắp xếp.

Ứng dụng của Binary Search

Binary Search có rất nhiều ứng dụng trong lập trình và các lĩnh vực khác, bao gồm:

  1. Tìm kiếm trong danh sách: Binary Search được sử dụng để tìm kiếm một phần tử cụ thể trong một danh sách đã được sắp xếp. Điều này rất hữu ích trong việc tìm kiếm nhanh chóng trong các tập dữ liệu lớn như cơ sở dữ liệu, danh bạ, tệp tin đã được sắp xếp, v.v.
  2. Tìm kiếm khoảng giá trị: Binary Search có thể được sử dụng để tìm kiếm khoảng giá trị trong một tập dữ liệu đã được sắp xếp. Ví dụ, trong việc tìm kiếm một phần tử lớn nhất nhỏ hơn một giá trị xác định hoặc tìm kiếm một phần tử nhỏ nhất lớn hơn một giá trị xác định.
  3. Tìm kiếm trong cây tìm kiếm nhị phân: Binary Search được sử dụng để thực hiện tìm kiếm trong cây tìm kiếm nhị phân. Các cây tìm kiếm nhị phân là cấu trúc dữ liệu phổ biến trong việc lưu trữ và tìm kiếm dữ liệu.
  4. Cắt tỉa trong các bài toán tối ưu: Binary Search cũng được sử dụng trong các bài toán tối ưu để tìm ra giá trị tối ưu trong một khoảng giá trị đã biết. Ví dụ, trong bài toán tìm kiếm điểm cắt tỉa của một đường thẳng với các đoạn thẳng khác.
  5. Tìm kiếm đa chiều: Binary Search có thể được mở rộng để tìm kiếm trong không gian nhiều chiều. Ví dụ, trong việc tìm kiếm trong một ma trận 2D đã được sắp xếp hoặc tìm kiếm trong không gian Euclide nhiều chiều.
  6. Các ứng dụng khác: Binary Search cũng được sử dụng trong các lĩnh vực khác như xử lý chuỗi, mã hóa và giải mã, kiểm tra tính sắp xếp của một tập dữ liệu, v.v.

Binary Search là một công cụ mạnh mẽ và quan trọng trong lập trình và giải quyết các vấn đề tìm kiếm.

Xem thêm Traversing Binary Trees

Ưu điểm và nhược điểm binary search c++

  • Ưu điểm:
    • Tìm kiếm nhanh, đặc biệt khi sử dụng với các mảng lớn vì chỉ duyệt qua một phần của mảng mà không cần duyệt qua toàn bộ mảng.
    • Dễ dàng sử dụng với các mảng đã được sắp xếp.
    • Sử dụng được với các kiểu dữ liệu khác nhau.
  • Nhược điểm:
    • Không hoạt động được với các mảng không được sắp xếp.
    • Không hoạt động tốt với các mảng có kích thước nhỏ.
    • Yêu cầu thêm bộ nhớ để lưu giá trị trung gian trong quá trình tìm kiếm.

Trong tổng quát, binary search là một thuật toán tìm kiếm rất hiệu quả và thường được sử dụng trong nhiều bài toán khác nhau, nhưng nó cũng có một số nhược điểm như không hoạt động tốt với các mảng không được sắp xếp hoặc có kích thước nhỏ. Ngoài ra, cũng cần phải sử dụng thêm bộ nhớ để lưu giá trị trung gian trong quá trình tìm kiếm.

Nếu bạn muốn sử dụng tìm kiếm nhị phân trong bài toán của mình, hãy chắc chắn rằng dữ liệu ban đầu đã được sắp xếp và kích thước mảng lớn để có hiệu quả tìm kiếm cao nhất.

Xem thêm Binary Operation

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now