5. 지수 검색

지수 검색에는 두 단계가 포함됩니다.

요소가 있는 범위 찾기

위의 발견 범위에서 이진 검색을 수행합니다.

요소가 존재할 수 있는 범위를 찾는 방법은 무엇입니까?

아이디어는 하위 배열 크기 1에서 시작하여 마지막 요소를 x와 비교한 다음 크기 2를 시도한 다음 하위 배열의 마지막 요소가 더 크지 않을 때까지 크기 4를 시도하는 것입니다.

인덱스 i를 찾으면(i의 반복된 두 배로) 요소가 i/2와 i 사이에 있어야 함을 압니다(이전 반복에서 더 큰 값을 찾을 수 없었기 때문에 i/2가 필요한 이유)

. 위 단계의 구현.


// Javascript program to find an element x
// in a sorted array using Exponential Search
  
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r] is
// present, otherwise -1
function binarySearch(arr, l, r, x)
{
    if (r >= l)
    {
        let mid = l + (r - l) / 2;
  
        // If the element is present
        // at the middle itself
        if (arr[mid] == x)
            return mid;
  
        // If element is smaller than
        // mid, then it can only be
        // present n left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
  
        // Else the element can only
        // be present in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
  
    // We reach here when element
    // is not present in array
    return -1;
}
 
 // Returns position of first
// occurrence of x in array
function exponentialSearch(arr, n, x)
{
      
    // If x is present at
    // first location itself
    if (arr[0] == x)
        return 0;
  
    // Find range for binary search
    // by repeated doubling
    let i = 1;
    while (i < n && arr[i] <= x)
        i = i * 2;
  
    // Call binary search for
    // the found range.
    return binarySearch(arr, i/2,
                       Math.min(i, n - 1), x);
}
     
 
// Driver Code
     
    let arr = [2, 3, 4, 10, 40];
    let n = arr.length;
    let x = 10;
    let result = exponentialSearch(arr, n, x);
    if (result == -1)
         document.write("Element is not present in array");
    else
        document.write("Element is present at index " + result);