Abhishek shah

Posted on

# 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;

}