Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
C
Embedded C
Java
SEO
HR
CS Subjects
CS Basics
O.S.
Networks
DBMS
Embedded Systems
Cloud Computing
Machine learning
CS Organizations
Linux
DOS
More...
Articles
Puzzles
News/Updates

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





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates



© https://www.includehelp.com (2015-2018), Some rights reserved.