Thuật Toán Exponential Search

Bài hôm nay chúng ta cùng tìm hiểu về thuật toán Exponential Search (Thuật toán tìm kiếm theo số mũ)

1. Nguyên lý Exponential Search

+ Cũng yêu cầu dãy số đầu vào là một dãy đã được xắp xếp cho sẵn.

+ Kết hợp với việc tìm kiếm theo kiểu nhị phân.

+ Tìm ra khoảng con chứa giá trị cần tìm kiếm, và sau đó sử dụng tìm kiếm nhị phân cho khoảng con đó.

Độ phức tạp thời gian mà nó đạt được là: Log2(n).

Step 1:

 

+ Kiểm tra phần tử 0 của tập để xem nó có phải là phần tử tìm kiếm hay không.

+ Nếu không thì bắt đầu giá trị chạy từ 1 và kiểm tra nó < giá trị cần tìm hay không.

=> Nếu có, thì tiếp tục tăng giá trị chạy lên theo công thức : i = i*2;

=> Nếu không, thì chứng tỏ giá trị cần tìm đang năm trong khoảng từ i/2 đến i  

Vì a[i] > X và vòng lặp trước đó là a[i/2] < X.

Do đó ta tìm được khoảng con chứa giá trị X cần tìm

Step 2:

Áp dụng Binary Search cho khoảng con vừa tìm được.

2 Thực hành.

// Phattrienphanmem123az.com
#include <iostream>
#include <conio.h>

int BinarySearch(int arr[], const int&, const int&, const int&);

int ExponentialSearch(int arr[], int n, int x)
{
  if (arr[0] == x)
    return 0;

  int i = 1;
  while (i < n && arr[i] <= x)
    i = i*2;
  return BinarySearch(arr, i/2, std::min(i, n), x);
}

int BinarySearch(int arr[], const int& l, const int& r, const int& x)
{
  if (r >= l)
  {
    int mid = l + (r - l)/2;

    if (arr[mid] == x)
      return mid;

    if (arr[mid] > x)
      return BinarySearch(arr, l, mid-1, x);

    return BinarySearch(arr, mid+1, r, x);
  }
  return -1;
}


int main(int argc, _TCHAR* argv[])
{
  int arr[] = {1, 3, 6, 7, 9, 11, 14, 33, 36};
  int n = sizeof(arr)/ sizeof(arr[0]);
  int x = 14;
  int ret = ExponentialSearch(arr, n, x);
  if (ret == -1)
    std::cout << "Khong tim dc";
  else
     std::cout << "Gia tri can tim tai vi tri: " << ret;
  _getch();
	return 0;
}

+ Phù hợp cho việc tìm kiếm các mảng có số lượng phần tử lớn, hoặc phần từ tìm kiếm nằm gần đầu danh sách, (Nhanh tìm ra tập còn chứa giá trị tìm kiếm).

TPham