Tìm kiếm nhị phân (ví dụ trên c++)

Ý tưởng tương tự thuật toán sắp xếp quá nổi tiếng QuickSort.

Sau mỗi bước tìm kiếm thì số phần tử trong lần xét sau chỉ còn 1 nửa. Cho nên thời gian thực thi của thuật tìm kiếm này là O(LogN).

sample:

 

<br />// mảng a chứa các phần tử đã được sắp xếp (điều kiện cần cho thuật toán này).

// n là số lượng phần tử trong mảng a này.

// x là phần tử cần tìm
int TimKiemNhiPhan(int a[MAX], int left, int right, int mid, int x)
{
if (left > right)return -1;
if (a[mid] == x)return mid;
if (a[mid] > x)return TimKiemNhiPhan(a, left, mid-1, (left+(mid-1))/2, x);
return TimKiemNhiPhan(a, mid + 1, right, (mid + 1 + right) / 2, x);
}

void Result()
{
int res = TimKiemNhiPhan(a, 0, n - 1, (n - 1) / 2, x);
if (vt == -1)
cout << "\nKhong tim thay"<<" "<< x;
else cout << "\nTim thay:"<<" "<<x << " "<<"tai vi tri la:" << vt;
}
Advertisements

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