Binary Search in array

Binary search is also a widely used searching technique used to find elements in an array. As the name suggests, binary search involves splitting the entire array into two pieces again and again until we find that we have searched for.Note: the array needs to be sorted first in order for this method to work.  In binary search, the starting, ending and middle positions are found out first. Then , the array is broken down into smaller and smaller pieces of two and the middle position is found out. The advantage of binary search is that it requires less no of passes through the array, making it a simple and efficient searching technique in an array compared to other searching techniques such as linear search.

 Consider the following code snippet :
// Program to search using binary search
#include <iostream.>

int main()
{
    int arr[20],position,value;
    int size,flag = 0;
    int beg,mid,end;
    mid = 0;
    // prompts the user to enter the maximum no of elements in the array
    std::cout<<" Enter the max no of elements you want in the array (max 20) : ";
    std::cin>>size;
    for (int i=0; i<size; i++)
    {
        std::cout<<"\n Element : "<<i<<" : ";
        std::cin>>arr[i];
    }
    std::cout<<"\n Enter the value that you want to search : ";
    std::cin>>value; // takes the value that is to be searched
    std::cin.ignore();
    beg = 0;
    end = size-1;
    mid = (beg+end)/2; // finds the middle index

    while ( beg <= end )
    {
          if ( arr[mid] == value ) // breaks loop if the element is found
          {
             position = mid;
             flag = 1;
             break;
             }
            
          else if ( arr[mid] > value )
               end = mid -1;
          else
              beg = mid + 1;
                     
        mid = (beg+end)/2; // finds the middle index at each pass
    } // end of while
   
     if ( flag == 1 ) // displays the found element
        std::cout<<"\n Value "<<value<<" found at position "<<position;
                         // displays an error if the element is not found
     else
         std::cout<<" \nVALUE NOT FOUND !!! ";
   
    std::cin.get();
    return 0;
} // end of main

Binary Search in array

Note : The array must be sorted beforehand for this technique to work.

------ Related Posts ------ 

Linear Search : http://programsplusplus.blogspot.in/2012/02/linear-search-in-array.html