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:

1. Set two variable 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.

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