Home »
Algorithms
Bitonic Search Algorithm
Here, we are going to learn about a special kind of searching algorithm which is known as bitonic search.
Submitted by Radib Kar, on November 08, 2018
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.
Let's check the algorithm for bitonic search...
Prerequisite: bitonic array of length n, input K
Algorithm
 Set two variable first=0 & last=n1

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==last1)
Check whether K is one of them or not//takes O(1) time
Else
Set a variable mid=first+(lastfirst)/2;
If(array[mid]==K)
Print that element is found & return
Else if (array[mid]<K)
Last=mid1;//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
 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.
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=n1,mid;
while(first<=last){
if(first==last){
if(a[first]==K)
return 1;
else
return 0;
}
else if(first==last1){
if(a[first]==K  a[last]==K)
return 1;
else
return 0;
}
else{
mid=first+(lastfirst)/2;
if(a[mid]==K)
return 1;
else if(a[mid]<K)
last=mid1;
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