What is Binary Search and why to use it?

Binary Search is a search algorithm. It is used to efficiently search for position of a particular number in a sorted array, character in an sorted String. It can also be used to search for first occurrences of a element or last occurrence. Most importantly it can only be used in case of sorted arrays or string.

Logic

In the start we calculate the middle position as

int s = 0, e = the length of array or string.
int mid = (s+e)/2;

Now after we have mid we have 3 case at hand.check if the element at the middle is greater or smaller than the element we are searching for (let say its X).

Case 1: arr[mid]>X

Then that means the element after the mid are also greater than X. So we can reduce the array in search from s to mid. So, we do e=mid-1;

Case 2: arr[mid]<X

Then that means the element before the mid are also smaller than X. So we can reduce the array in search from mid + 1 to e. So, we do s=mid+1;

Case 3: arr[mid]==X

When we finally got the position of X.

Here is a code to show how it

int binarySort(int arr[],int X){
  int arr=[1,2,3,4,5,6,7,8,9]; // A sorted Array of length n
  int s = 0,e = n-1;

  while(s<=e){
   int mid = (s+e)/2;
   if(arr[mid] > X) e = mid - 1;
   else if (arr[mid] < X) s = mid + 1;
   else return mid;
  }
  return -1;
}

To Find First Occurrence or Last Occurrence

When we find the position of X we have to new condition for First Occurrence and Last Occurrence.

First Occurrence:

Check if there is the same element present at mid - 1 position if yes then you would have to decrease the search space. in the case of First Occurrence or mid + 1 position in case of Last Occurrence

   else{
     if(arr[mid-1] != arr[mid] or mid == 0)
          return mid;
     else 
          e = mid - 1;

   }

Last Occurrence:

Check if there is the same element present at mid + 1 position if yes then you would have to decrease the search space
by making s = mid+1;

   else{
     if(arr[mid+1] != arr[mid] or mid == n-1)
          return mid;
     else 
          s = mid + 1;

   }

If you have anything to add do suggest in the comments.