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

## Top comments (0)