How does binary search work

Given an array of numbers, how do you search for a number? 
The simplest method is to start at the first element and keep comparing until the end of the array. If it is found anywhere in the middle, return it. Otherwise we would reach the end of the array which indicates that the element in not found in the array. This is called linear search. Since this algorithm examines all the elements in the worst case, it’s time complexity is O(n).

Binary search on the other hand runs in O(log n) which is better compared to linear search. Binary search requires the input array to be sorted. 

Binary search starts by dividing the array in two halves. Then we compare the search element with the middle element, if it matches, we return that index. If the middle element is less than the search element, then we can ignore the left half of the array because all the elements which precede middle are far away from the search element. Hence we can confine our search to the right half only. Similarly if the middle element is greater than the search element, no need to search the right half. We can confine our search to the left half only. The same procedure is repeated until we find the element or, the array size becomes 1.

Let us look at an example to understand this algorithm
Let us consider the input array as [1,2,3,4,5,6,7,8,9] and we want to search for 6. Here is how the algorithm works

step 1: [1,2,3,4,(5),6,7,8,9] – middle element is 5 which is less than 6. So skipping the left half
step 2: [6,(7),8,9] – middle element is 7 which is greater than 6. So skipping right half
step 3: [6] – middle element is 6. match found, so return it.

#include <iostream>
using namespace std;
int array[100];
//takes the following parameters 

//s: search element, lower index, higher index

int bin_search(int s, int low, int high)
{
 while( low <= high)
 {
  // the middle element
  int middle = (low + high)/2;
  //if match is found, return it
  if( array[middle] == s)
   return middle;
  
  //if middle element is less
  else if ( array[middle] < s)
  {
   //search the right half
   low = middle+1;
  }
  else
  {
   //search the left half
   high = middle-1;
  }
 }
    return -1;
}
int main()
{
 int n; // array size
 cin>>n;
 int i;
 for( i = 0 ; i < n ; i++)
 {
  cin>>array[i];
 }
 //search element
 int s;
 cin>>s;
 
 cout<<s<<" found at: "<<bin_search(s,0,n-1);
 return 0;
}