Algorithms Posted 6 months ago

Binary Search is a simple and efficient search algorithm that works on a given set of elements to find the occurrence of a target search interest. The prerequisite of this search algorithm is that the target set of elements on which it operates should be a sorted set (in some order).

The algorithm improves over the traditional linear search approach where you just loop through all the elements in the set and do a one-on-one comparison on the current element on the set with the target element, such that while a traditional linear search takes O(N) time to perform the search operation in its worst-case, the Binary Search does it in *O(logN)* time.

Let's start by understanding how a linear search works and then see how Binary Search scores against this:

**The Simplest Search - Linear Search:**

For a given set A containing N elements, we need to find the index at which the target element E occurs in the set. The linear search does it as below:

```
function LinearSearch(array A, integer N, integer E)
begin
currentIndex = 0
while currentIndex < N do
begin
if A[currentIndex] == E then
begin
return currentIndex // a match found
end
else
begin
currentIndex = currentIndex + 1
end
end
return -1 // no matching element was found
end
```

In this algorithm, the time taken for the lookup grows linearly as the input set A grows in size. Hence the worst case complexity of this search is O(N) where N is the number of elements in the set.

**Improving on the Linear Search - Search by Half-Intervals:**

In case of a BinarySearch, we know that the set is already sorted. Hence, for any given iteration, we examine only "half" of the given input set for the target element and if it is not found, we'll further reduce the lookup to smaller subsets, until we run out of the elements. The mechanism is like below:

- Define leftIndex and rightIndex for the input set on which the lookup happens.
- Determine the midpoint of this set midIndex = Average(left, right)
- Check if the targetElement is present at this midIndex or not. If present, the search ends with the midIndex as the required output
- if the midIndex doesn't contain the targetElement, check if the element at midIndex is less than or greater than the targetElement
- if the targetElement is less than the element at midIndex, it means the element might exist to the "left" of the midIndex, otherwise "right".
- At this point, the algorithm reduces the set to lookup for the targetElement either to the "left" subset or "right" subset of the midIndex.
- The algorithm further continues till the leftIndex and the rightIndex overlap with each other, which means the element doesn't exist.

We can implement this in a regular loop:

```
function BinarySearch(array A, integer leftIndex, integer rightIndex, integer target)
begin
while leftIndex > rightIndex do
begin
midIndex = (leftIndex + rightIndex) / 2
if A[midIndex] == target then
begin
return midIndex // element found
end
else if A[midIndex] > target then // element falls on the left subset
begin
right = midIndex - 1
end
else
begin
left = midIndex
end
end
return -1 // element not found
end
```

Or in a recursive fashion:

```
function BS_Recursive(array A, integer leftIndex, integer rightIndex, integer target)
begin
if leftIndex > rightIndex then
begin
return -1
end
midIndex = (leftIndex + rightIndex) / 2
if A[midIndex] == target then
begin
return midIndex // element found
end
if A[midIndex] > target then // element falls on the left subset
begin
return BS_Recursive(A, left, mid - 1, target)
end
else
begin
return BS_Recursive(A, mid, right, target)
end
end
```

**Implementation in C# (Looping and Recursive):**

```
public int DoBinarySearch(int[] array, int left, int right, int searchElement)
{
if (left > right) return -1;
int mid = (left + right) / 2;
if (array[mid] == searchElement) return mid;
if (array[mid] > searchElement)
return DoBinarySearch(array, left, mid - 1, searchElement);
else
return DoBinarySearch(array, mid, right, searchElement);
}
#Invoking#
DoBinarySearch(array, 0, array.Length - 1, searchElement);
```

```
public int DoBS_NoRecursion(int[] array, int left, int right, int searchElement)
{
while (left < right)
{
var mid = (left + right) / 2;
if (array[mid] == searchElement) return mid;
if (array[mid] > searchElement)
{
right = mid - 1;
}
else
{
left = mid;
}
}
return -1;
}
#Invoking#
DoBS_NoRecursion(array, 0, array.Length - 1, searchElement);
```

**Complexity Analysis:**

As we can see, for every iteration (or recursion), the algorithm works on exactly "half" of the initial subset that the algorithm works at the beginning. And hence we have the time taken can be written as:

```
T(n) = T(n/2) + c // where c is a constant time taken for the comparison
```

When we expand on this relation for every branch of the call tree, the total work done is equal to the depth of the tree which is O(logN). Hence the total time taken for this search operation always lies within O(logN).

**Final Thoughts:**

Although BinarySearch is an efficient search algorithm, the prerequisite that it can work only on a sorted set of elements makes it less efficient over larger datasets. When a sorted set of elements are involved for lookup, datastructures such as HashTables can manage to keep the lookup time for as less as O(1) when compared to O(logN) in this case.

But the implementation of the BinarySearch finds several usecases such as finding the possible position for an insertion, and so on. And this algorithm also gives way to some of the other divide and conquer algorithms such as QuickSort and MergeSort which work in a similar fashion and take O(NlogN) time for sorting.