지수 검색

1. 지수 검색 알고리즘
2. 지수 검색 예
3. 지수 검색 알고리즘 구현
4. 지수 검색 알고리즘 복잡성

이중 검색 또는 손가락 검색이라고도하는 지수 검색은 거대한 크기의 배열에서 요소를 검색하기 위해 만들어진 알고리즘입니다. 이것은 2 단계 과정입니다. 먼저 알고리즘은 타겟 요소가있는(L, R)범위를 찾고이 범위 내에서 이진 검색을 사용하여 타겟의 정확한 위치를 찾습니다.

인덱스pow(2, k)의 요소가 목표보다 큰 첫 번째 지수k를 검색하여 범위 보유 요소를 찾기 때문에 지수 검색이라고합니다. 이름은 지수 검색이지만이 알고리즘의 시간 복잡도는 로그입니다. 배열의 크기가 무한하고 이진 검색보다 훨씬 빠르게 솔루션에 수렴 할 때 매우 유용합니다.

지수 검색 알고리즘

n요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정하고X요소를 찾으려고합니다.

지수 검색 예

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)배열이 있고 X-10을 찾고 싶다고 가정합니다.

지수 검색 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

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, min(i, n - 1), x);
}

int main() {
  int n = 11;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
  int x = 10;
  int result = exponentialSearch(arr, n, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

지수 검색 알고리즘 복잡성

시간 복잡성

• 평균 사례

평균 케이스 시간 복잡도는O(logi)입니다. 여기서i는 배열 내 대상 요소X의 인덱스입니다. 요소가 배열의 시작 부분에 가까워지면 이진 검색보다 성능이 뛰어납니다.

• 베스트 케이스

가장 좋은 경우는 비교하는 요소가 검색중인 요소이고 첫 번째 반복에서 반환 될 때 발생합니다. 최상의 경우 시간 복잡도는O(1)입니다.

• 최악의 경우

최악의 시간 복잡성은 평균 시간 복잡성과 동일합니다. 최악의 시간 복잡도는O(logi)입니다.

공간 복잡성

이 알고리즘의 공간 복잡도는 임시 변수 외에 추가 공간이 필요하지 않기 때문에O(1)입니다.