Home > Algorithm > Tìm kiếm nhị phân – Binary Search

Tìm kiếm nhị phân – Binary Search

1. Giới thiệu

Trong khoa học máy tính, tìm kiếm nhị phân ( binary search ) là một thuật toán dùng để tìm kiếm phần tử trong một danh sách đã sắp xếp ( sorted lists and array ).

Ý tưởng :  So sánh phần tử cần tìm với phần tử nằm chính giữa danh sách để xác định vùng dữ liệu có chứa giá trị cần tìm. Nếu 2 phần tử bằng nhau thì thuật toán kết thúc. Nếu 2 phần tử không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa đầu hoặc nửa sau của danh sách.

Vì sau mỗi bước tìm kiếm, miền dữ liệu cần xét giảm đi một nửa nên thời gian thực thi của thuật toán là hàm logarit.

2. Cài đặt

/// <summary>
/// Thuật toán tìm kiếm nhị phân trong 1 mảng đã sắp xếp
/// </summary>
/// <param name="value">Giá trị cần tìm</param>
/// <param name="arr">Mảng đã sắp xếp</param>
/// <returns></returns>
public int BinarySearch(int value, int[] arr)
{
    int left = 0, right = arr.Length, mid;
    int ret = -1;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (arr[mid] == value)
        {
            ret = mid;
            break;
        }
        else if (arr[mid] > value)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
     }
     return ret;
 }

3. Độ phức tạp thuật toán

– Tốt nhất : O(1) – Phần tử cần tìm ở chính giữa danh sách

– Xấu nhất : O(log2(n)) – Không có phần tử cần tìm trong danh sách

– Trung bình : O(log2(n/2)) – Xác suất các phần tử trong danh sách chứa giá trị cần tìm là như nhau.

 

Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: