Экспоненциальный поиск
Опубликовано: 20 Января, 2022
Название этого алгоритма поиска может вводить в заблуждение, поскольку он работает за время O (Log n). Название происходит от способа поиска элемента.
Учитывая отсортированный массив и элемент x, который должен быть поиск, найти позицию x в массиве. Ввод: arr [] = {10, 20, 40, 45, 55} х = 45 Выход: элемент найден с индексом 3 Ввод: arr [] = {10, 15, 25, 45, 55} х = 15 Выход: элемент найден с индексом 1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Мы обсудили линейный поиск, бинарный поиск для этой проблемы.
Экспоненциальный поиск состоит из двух этапов:
- Найдите диапазон, в котором присутствует элемент
- Выполните двоичный поиск в указанном выше диапазоне.
How to find the range where element may be present?
The idea is to start with subarray size 1, compare its last element with x, then try size 2, then 4 and so on until last element of a subarray is not greater.
Once we find an index i (after repeated doubling of i), we know that the element must be present between i/2 and i (Why i/2? because we could not find a greater value in previous iteration)
Given below are the implementations of above steps.
C++
// C++ program to find an element x in a // sorted array using Exponential search. #include <bits/stdc++.h> using namespace std; int binarySearch( int arr[], int , int , int ); // Returns position of first occurrence of // x in array int exponentialSearch( int arr[], int n, int x) { // If x is present at firt location itself if (arr[0] == x) return 0; // Find range for binary search by // repeated doubling int i = 1; while (i < n && arr[i] <= x) i = i*2; // Call binary search for the found range. return binarySearch(arr, i/2, min(i, n-1), x); } // A recursive binary search function. It returns // location of x in given array arr[l..r] is // present, otherwise -1 int binarySearch( int arr[], int l, int r, int x) { if (r >= l) { int 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; } // Driver code int main( void ) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof (arr)/ sizeof (arr[0]); int x = 10; int result = exponentialSearch(arr, n, x); (result == -1)? printf ("Element is not present in array") : printf ("Element is present at index %d", result); return 0; } |
Java
// Java program to // find an element x in a // sorted array using // Exponential search. import java.util.Arrays; class GFG { // Returns position of // first occurrence of // x in array static int exponentialSearch( int arr[], int n, int x) { // If x is present at firt location itself if (arr[ 0 ] == x) return 0 ; // Find range for binary search by // repeated doubling int i = 1 ; while (i < n && arr[i] <= x) i = i* 2 ; // Call binary search for the found range. return Arrays.binarySearch(arr, i/ 2 , Math.min(i, n- 1 ), x); } // Driver code public static void main(String args[]) { int arr[] = { 2 , 3 , 4 , 10 , 40 }; int x = 10 ; int result = exponentialSearch(arr, arr.length, x); System.out.println((result < 0 ) ? "Element is not present in array" : "Element is present at index " + result); } } |
Python
# Python program to find an element x # in a sorted array using Exponential Search # A recurssive binary search function returns # location of x in given array arr[l..r] is # present, otherwise -1 def binarySearch( arr, l, r, x): if r > = l: mid = l + ( r - l ) / 2 # If the element is present at # the middle itself if arr[mid] = = x: return mid # If the element is smaller than mid, # then it can only be present in the # left subarray if arr[mid] > x: return binarySearch(arr, l, mid - 1 , x) # Else he element can only be # present in the right return binarySearch(arr, mid + 1 , r, x) # We reach here if the element is not present return - 1 # Returns the position of first # occurrence of x in array def exponentialSearch(arr, n, x): # IF x is present at first # location itself if arr[ 0 ] = = x: return 0 # Find range for binary search # j by repeated doubling i = 1 while i < n and arr[i] < = x: i = i * 2 # Call binary search for the found range return binarySearch( arr, i / 2 , min (i, n - 1 ), x) # Driver Code arr = [ 2 , 3 , 4 , 10 , 40 ] n = len (arr) x = 10 result = exponentialSearch(arr, n, x) if result = = - 1 : print "Element not found in thye array" else : print "Element is present at index %d" % (result) # This code is contributed by Harshit Agrawal |
C#
// C# program to find an element x in a // sorted array using Exponential search. using System; class GFG { // Returns position of first // occurrence of x in array static int exponentialSearch( int []arr, int n, int x) { // If x is present at // first location itself if (arr[0] == x) return 0; // Find range for binary search // by repeated doubling int 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); } // A recursive binary search // function. It returns location // of x in given array arr[l..r] is // present, otherwise -1 static int binarySearch( int []arr, int l, int r, int x) { if (r >= l) { int 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; } // Driver code public static void Main() { int []arr = {2, 3, 4, 10, 40}; int n = arr.Length; int x = 10; int result = exponentialSearch(arr, n, x); if (result == -1) Console.Write("Element is not present in array"); else Console.Write("Element is present at index " + result); } } // This code is contributed by Smitha |
PHP
<?php // PHP program to find an element x in a // sorted array using Exponential search. // 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 $i = 1; while ( $i < $n and $arr [ $i ] <= $x ) $i = $i * 2; // Call binary search // for the found range. return binarySearch( $arr , $i / 2, min( $i , $n - 1), $x ); } // 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 ) { $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; } // Driver code $arr = array (2, 3, 4, 10, 40); $n = count ( $arr ); $x = 10; $result = exponentialSearch( $arr , $n , $x ); if ( $result == -1) echo "Element is not present in array" ; else echo "Element is present at index " , $result ; // This code is contributed by anuj_67 ?> |
Javascript
<script> // 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 locati
РЕКОМЕНДУЕМЫЕ СТАТЬИ |