雙向a*搜索算法

什么是雙音搜索？ (What is bitonic search?)

Searching a bitonic array is known as bitonic search. An array is said to be bitonic if it has an increasing sequence of integers followed immediately by a decreasing sequence of integers.

搜索雙音陣列稱為雙音搜索 。 如果數組具有遞增的整數序列，緊隨其后的是遞減的整數序列，則稱其為雙偶數 。

Given a bitonic array our work is to search a given input element in the bitonic array. In case of minimum time complexity we can think of linear search in O(n) time but bitonic search takes only O(logn) steps to complete the searching.

給定一個雙調陣列我們的工作是雙調數組中搜索給定的輸入元素。 在最小時間復雜度的情況下，我們可以考慮在O(n)時間內進行線性搜索，但雙音位搜索僅需O(logn)步驟即可完成搜索。

Let's check the algorithm for bitonic search...

讓我們檢查一下雙音搜索的算法...

Prerequisite: bitonic array of length n, input K

先決條件：長度為n的雙音陣列，輸入K

Algorithm:

算法：

1. Set two variable first=0 & last=n-1

   設置兩個變量first = 0和last = n-1

2.     While(first<=last){
   If(first==last)     //array has size 1
   Check whether the only element is Kor not   // takes O(1) time
   Else if (first==last-1)
   Check whether K is one of them or not//takes O(1) time
   Else
   Set a variable mid=first+(last-first)/2;
   If(array[mid]==K)
   Print that element is found & return
   Else if (array[mid]<K)
   Last=mid-1;//as the element is greater than array[mid] we need to
   //reach the increasing sequence
   Else
   First=mid+1; //as the element is less than array[mid] we need to
   //reach the decreasing sequence
   End while loop
   
   

3. If the element is in the array then the function will return from the loop to main function. If the element is not in the array they the program will come out of the loop and print that the element is missing.

   如果元素在數組中，則函數將從循環返回到主函數。 如果該元素不在數組中，則程序將退出循環并顯示該元素丟失。

Discussion:

討論：

It's clear that we are not searching the whole array. Rather we are partitioning every time based on the value comparison between array[mid] and input, K. Thus it requires O(logn) steps to complete the search.

顯然，我們并沒有搜索整個數組。 而是每次都基于array [mid]與輸入K之間的值比較進行分區。 因此，它需要O(logn)步驟才能完成搜索。

Bitonic搜索的C ++實現 (C++ implementation of the Bitonic Search)

#include<bits/stdc++.h>
using namespace std;
int findelements(int* a, int n,int K){
int first=0,last=n-1,mid;
while(first<=last){
if(first==last){
if(a[first]==K)
return 1;
else
return 0;
}
else if(first==last-1){
if(a[first]==K || a[last]==K)
return 1;
else
return 0;
}
else{
mid=first+(last-first)/2;
if(a[mid]==K)
return 1;
else if(a[mid]<K)
last=mid-1;
else 
first=mid+1;
}
}
return 0;
}
int main(){
int K,count=0,n;
cout<<"enter no of elements\n";        // enter array length
cin>>n;
int* a=(int*)(malloc(sizeof(int)*n));
cout<<"enter elements................\n";  //fill the array
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
cout<<"enter the element to search,K"<<endl;
cin>>K;
if(findelements(a,n,K))
cout<<"element is found\n";
else
cout<<"element not found\n";
return 0;
}

Output (first run)

輸出(首次運行)

enter no of elements 
10 
enter elements................ 
1
2
3
4
5
4
3
2
1
0
enter the element to search,K
3
element is found 

Output (second run)

輸出(第二次運行)

enter no of elements 
10 
enter elements................ 
1
2
3
4
5
6
5
4
3
2
enter the element to search,K
10 
element not found

翻譯自: https://www.includehelp.com/algorithms/bitonic-search.aspx

雙向a*搜索算法