搜索国彩网5：指数搜索

指数搜索是对二进制搜索的改进。当我们有大量数据时，将使用此国彩网。

在指数搜索国彩网中，我们使用二进制搜索。但不同之处在于，我们获得了要搜索的元素范围，并将其作为二进制搜索的输入。

现在我们如何选择元素范围？

最初我们从“1”。然后，对于每遍，我们每次都会增加2次间隔。

一旦获得范围，就将该范围作为二进制搜索的输入。

int exponential_search(arr[], int size, int key)
{

    int 界= 1;
    while (bound < size && arr[bound] < key) 
    {
    //for every pass, increase the gap 2 times.
        界*= 2;
    }

    return binary_search(arr, key, bound/2, min(bound + 1, size));
}

 

让我们借助示例来了解此国彩网

考虑数组：

arr [] = {1,2,3,4,5,6,7,8};

搜索关键字= 7；

Initially, the 界value will be 1 for pass 1, now check “bound < size && arr[bound] < key” ? It is true. because 界= 1 that is less than 8 and arr[1] < key.

Now, the 界value will be 2 for pass 2, now check “bound < size && arr[bound] < key” ? It is true. because 界= 2 that is less than 8 and arr[2] < key.

Now, the 界value will be 4 for pass 3, , now check “bound < size && arr[bound] < key” ? It is true. because 界= 4 that is less than 8 and arr[4] < key.

现在，第4遍的绑定值为8，现在检查“bound < size && arr[bound] < key” ? It is false. because 界= 8 that is not less than 8. Hence exit the loop.

然后，我们通过调用binary_search（arr，key，bound / 2，min（bound + 1，size））执行二进制搜索。

as 界is 8, bound/2 = 4.

min（8 + 1，8）= 8

现在我们将二进制搜索称为binary_search（arr，7，4，8）;

现在我们知道存在关键元素的元素的确切范围。现在，我们在该范围内执行二进制搜索，如果没有找到该元素，则返回。

#include<iostream>
#include <vector>

using namespace std;


void binarySearch(int arr[], int start, int end, int key) 
{ 
  if (end >= start) 
  { 
    int mid = start + (end - start)/2; 

    if (arr[mid] == key)
    {
      cout<<"Element found"<<endl;
      return; 
    }

    if (arr[mid] > key) 
      return binarySearch(arr, start, mid-1, key); 

    return binarySearch(arr, mid+1, end, key); 
  }

  cout<<"Element NOT found"<<endl;
  return; 
} 



void exponential_search(int arr[], int size, int key) 
{ 
  if (arr[0] == key)
  {
    cout<<"Element found"<<endl;
    return; 
  }

  int 界= 1; 
  while (bound < size && arr[bound] <= key)
  {
    cout<<"Bound = "<<bound<<endl;
    界= bound*2; 
  }

  binarySearch(arr, bound/2,  min(bound + 1, size), key);
  return; 
} 


int main() 
{  
    int arr [] = {1,2,3,4,5,6,7,8};
    int len = 8;
    int key = 7;

    exponential_search(arr, len, key);

    return 0; 
}

Element found

在最坏的情况下，该国彩网的时间复杂度将为O（log i）。

进一步阅读：

AJ关于DS和国彩网的权威指南。单击此处以学习国彩网和数据结构教程的完整列表。 85多个章节可供学习。