보간 검색

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

보간 검색은 빠르고 효율적인 검색 알고리즘입니다. 배열 요소가 정렬 된 배열에 균일하게 분산되는 시나리오에 대한 이진 검색 알고리즘을 개선합니다. 필요한 값의 프로빙 위치에서 작동합니다. 이진 검색과 달리 항상 배열의 중간으로 이동하지는 않지만 검색 할 키의 값에 따라 임의의 위치로 이동할 수 있습니다. 추정 된 위치의 값을 비교하고 검색 공간을 전후 부분으로 줄입니다. 예를 들어, 사전에서 단어를 검색 할 때 매번 검색 공간을 두 개로 나누지 않고 그 안에있는 글자의 위치에 따라 페이지를 넘깁니다.

보간 검색 알고리즘

n요소를 포함하는 정렬되지 않은 배열A[]가 있고 주어진 요소X를 찾고 싶다고 가정 해 보겠습니다.

보간 검색 예

배열이(1, 3, 7, 8, 11, 15, 17, 18, 21)이고 X-18을 찾고 싶다고 가정합니다.

보간 검색 알고리즘 구현

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

int interpolation_search(int arr[], int n, int X) {
  int lo = 0;
  int hi = n - 1;
  int mid;

  while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
    mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

    if (arr[mid] < X)
      lo = mid + 1;
    else if (X < arr[mid])
      hi = mid - 1;
    else
      return mid;
  }

  if (X == arr[lo])
    return lo;
  else
    return -1;
}

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

보간 검색 알고리즘 복잡성

시간 복잡성

• 평균 사례

알고리즘의 평균 케이스 시간 복잡도는O(log(logn))의 순서입니다. 배열 내부의 모든 요소가 균일하게 분포 될 때 발생합니다.

• 베스트 케이스

가장 좋은 경우는 우리가 검색하는 요소가 보간 검색에 의해 탐색 된 첫 번째 요소 일 때 발생합니다. 알고리즘의 최상의 경우 시간 복잡도는O(1)입니다.

• 최악의 경우

최악의 경우는 목표의 숫자 값이 기하 급수적으로 증가 할 때 발생합니다. 알고리즘의 최악의 경우 시간 복잡도는O(n)입니다.

공간 복잡성

이 알고리즘의 공간 복잡성은 임시 변수 이외의 데이터 구조가 필요하지 않기 때문에O(1)입니다.