Binary Search Algorithm

binary search algorithm (or binary chop) is a technique for locating a particular value in a sorted list. The method makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the span (which, because the list is in sorted order, is the median value), comparing its value to the target value, and determining if it is greater than, less than, or equal to the target value. A guessed index whose value turns out to be too high becomes the new upper bound of the span, and if its value is too low that index becomes the new lower bound. Only the sign of the difference is inspected: there is no attempt at an interpolation search based on the size of the difference.Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.First, the search item is compared with the middle element of the list. If the search item is less than the middle item of the list, we restrict the search to the upper half of the list; otherwise, we search the lower half of the list.Algorithm.First, the middle element of the sequence is compared to the value we are searching for. If this element matches the value we are searching for, we are done. If, however, the middle element is ``less than'' the value we are chosen for (as specified by the relation used to specify a total order over the set of elements), then we know that, if the value exists in the sequence, it must exist somewhere after the middle element. Therefore we can eliminate the first half of the sequence from our search and simply repeat the search in the exact same manner on the remaining half of the sequence. If, however, the value we are searching for comes before the middle element, then we repeat the search on the first half of the sequence.

Loop for Binary Search

#include 

int binarySearch(int sortedArray[], int first, int last, int key) {
// function:
//   Searches sortedArray[first]..sortedArray[last] for key.
// returns: index of the matching element if it finds key,
//         otherwise  -(index where it could be inserted)-1.
// parameters:
//   sortedArray in  array of sorted (ascending) values.
//   first, last in  lower and upper subscript bounds
//   key         in  value to search for.
// returns:
//   index of key, or -insertion_position -1 if key is not
//                 in the array. This value can easily be
//                 transformed into the position to insert it.

   while (first <= last) 
{
       int mid = (first + last) / 2;  // compute mid point.
       if (key > sortedArray[mid]) 
           first = mid + 1;  // repeat search in top half.
       else if (key < sortedArray[mid]) 
           last = mid - 1; // repeat search in bottom half.
       else
           return mid;     // found it. return position /////
   }
   return -(first + 1);    // failed to find key
}

Source code

using System;
class binSearch
{
public static void Main()
{
int[] a= new int[100];
Console.WriteLine("Number of elements in the array ?");
string s=Console.ReadLine();
int x=Int32.Parse(s);
Console.WriteLine("-----------------------");
Console.WriteLine(" Enter array elements ");
Console.WriteLine("-----------------------");
for(int i=0;i<x;i++)
{
string s1=Console.ReadLine();
a[i]=Int32.Parse(s1);
}
Console.WriteLine("--------------------");
Console.WriteLine("Enter Search element");
Console.WriteLine("--------------------");
string s3=Console.ReadLine();
int x2=Int32.Parse(s3);
int low=0;
int high=x-1;
while(low<=high)
{
int mid=(low+high)/2;
if(x2<a[mid])
high=mid-1;
else if(x2>a[mid])
low=mid+1;
else if(x2==a[mid])
{
Console.WriteLine("-----------------");
Console.WriteLine("Search successful");
Console.WriteLine("-----------------");
Console.WriteLine("Element {0} found at location {1}\n",x2,mid+1);
return;
}
}
Console.WriteLine("Search unsuccessful");
}
}