BINARY SEARCH

WHAT IS BINARY SEARCH?

Binary Search is defined as a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to
O(log N). 

HOW BINARY SEARCH WORKS ?

Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23. 

First Step: 

Initially the search space is from 0 to 9. 

Let’s denote the boundary by L and H where L = 0 and H = 9 initially. 

Now mid of this search space is M = 4. 

So compare target with arr[M].

Second Step: 

As arr[4] is less than target, switch the search space to the right of 16, i.e., [5, 9]. 

Now L = 5, H = 9 and M becomes 7. 

Compare target with arr[M].

Third Step: 

arr[7] is greater than target. 

Shift the search space to the left of M, i.e., [5, 6]. 

So, now L = 5, H = 6 and M = 6. 

Compare arr[M] with target. 

Here arr[M] and target are the same. 

So, we have found the target.

" CODE OF A BINARY SEARCH "

WHEN TO USE BINARY SEARCH ?

When searching a large dataset as it has a time complexity of O(log n), which means that it is much faster than linear search.

When the dataset is sorted.

When data is stored in contiguous memory.

Data does not have a complex structure or relationships.

HOW TO IMPLEMENT BINARY SEARCH ? 

The basic steps to perform Binary Search are:

Set the low index to the first element of the array and the high index to the last element.

Set the middle index to the average of the low and high indices.

If the element at the middle index is the target element, return the middle index.

Otherwise, based on the value of the key to be found and the value of the middle element, decide the next search space.

If the target is less than the element at the middle index, set the high index to middle index – 1.

If the target is greater than the element at the middle index, set the low index to middle index + 1.