Binary Search Algorithm C++

Binary Search Algorithm C++

Binary Search Algorithm in C++

Binary Search Algorithm in C++

Binary search algorithm in C++ relies on a divide and conquer strategy to find a value within an already-sorted collection. Binary search locates the position of an item in a sorted array. Binary search compare an input search key to the middle element of the array and the comparison determines whether the element equals the input, less than the input or greater. The return value is the element position in the array.

Bibary Search Algorithm complexity

  • Worst case performance O(log n)
  • Best case performance O(1)
  • Average case performance O(log n)
  • Worst case space complexity O(1)

Binary Search Algorithm Arrays implementation

#include <cstdlib>
#include <iostream>
using namespace std;

int binary_search(int array[],int first,int last, int value);

int main() {

int list[10];

 for (int k=0; k<11; k++)
 list[k]=2*k+1;

 cout<< "binary search results: "<< binary_search(list,1,21,11)<<endl;

 return 0;
}//end of main
int binary_search(int array[],int first,int last, int search_key)
{
 int index;

 if (first > last)
 index = -1;

 else
 {
 int mid = (first + last)/2;

 if (search_key == array[mid])
 index = mid;
 else

 if (search_key < array[mid])
 index = binary_search(array,first, mid-1, search_key);
 else
 index = binary_search(array, mid+1, last, search_key);

 } // end if
 return index;
 }// end binarySearch

program output

My array contains: 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
binary search found value 26 at position: 13

You must be logged in to post a comment.

Proudly powered by WordPress   Premium Style Theme by www.gopiplus.com
%d bloggers like this: