Binary Search-Pseudocode with Example and Program

    Binary search is most common and simple technique use to search specific number in array. Binary search requires sorted array  hence the complexity of binary search O(log n) is better than most of the searching algorithm.binary search first compare the search value with middle element of array if match found then program terminates.if search value is smaller than middle element then it will search that value in left part of array otherwise it will search that value in right part of array.

 Space complexity: O(1)

 Time complexity:

Best case	Average case	Worst case
O(1)	O(log n)	O(log n)

Example of  Binary search:
search element 20 from below array:

         10    20    30    40    50    60    70

here,

  start=0  and end=6 

  mid=(0+6)/2=3

  element at 3rd index(40) is middle element
  search element is 30
                        30 < 40
 now,
 start=0 and  end=mid-1=2
 mid=(start+end)/2=1
 element at 1st index is middle element
 thus search element 20 is found at 1st index position.

Pseudo-code:

  procedure binary_search
   A = sorted array
   n = size of array
   x = value to be searched
   Set first= 1
   Set last= n 

   while x not found
      if last < first 
      EXIT: x does not exists.
      set mid = first + last  / 2      
      if  x > A[mid]
         set first= mid + 1         
      
      if  x < A[mid]
         set last = mid - 1

      if A[mid] = x 
         EXIT: x found at location mid
   end while
end procedure


program of binary search:

#include <iostream>
using namespace std;
int main()
{
int n,arr[10];
cout<<"\n No. of elements ";
cin>>n;
cout<<"\Enter the elements in sorted order";
for(int i=0; i<n; i++)
{
cin>>arr[i];
}
int value, first, mid, last;
cout<<"\nEnter the value to search: ";
cin>>value;
first = 0;
last = n-1;
mid = (first+last)/2;
while(first<=last)
{
if(arr[mid]==value)
{
cout<<"\n value found at index "<<mid;
break;
}
else if(value < mid)
{
last = mid-1;
mid = (first+last)/2;
}
else if(value > mid)
{
first = mid+1;
mid = (first+last)/2;
}
}
if(first>last)
cout<<"\n value not found in the list";
return 0;
}

Output:

Output of binary search program