Algorithms Every Developer Should Know - Binary Search

In this new series "Algorithms Every Developer Should Know", I'm going to explore the implementation of algorithms everyone should know (if you need them, otherwise it's fine) using C#. For the first post, we will take a look at Binary Search, a search algorithm used to find the position of a specific value in a sorted array.

Using an iterative or recursive approach, we can implement the binary search algorithm, and we'll take a look at both of them.

Table Of Contents

• Binary Search Algorithm
  • Definition
  • Time Complexity
  • Auxiliary Space
  • Step by Step pseudo-code
  • Edge Cases
• Implementation of the Binary Search Algorithm using an iterative approach
• Implementation of the Binary Search Algorithm using an iterative approach
• Generic implementation of the binary search algorithm in C#
• Explore the code

Binary Search Algorithm

Definition

Search a sorted array by repeatedly dividing the search interval in half. This algorithm is useful in finding the position of a specific value in a sorted array.

Time Complexity

O(logN)

Not going into detail but, but this tells us that for an array with N = 8, the output of logN is 3, which means we can split the array 3 times, so the number of steps (at most) to find the target value will be (3 + 1) = 4. Where 1 is the first attempt and also the best-case scenario in which the middle element of the array is our target value.

Auxiliary Space

O(1)

The constant space of 1 tells us that the algorithm does not require temporary additional memory allocations to do its work.

A step by step look at the algorithm

Starting with the middle element:

• 1. If the target value is equal to the middle element of the array, then return the index of the middle element -> [goto 3].
• 2. If not, then compare the middle element with the target value;
  • 2.1 If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and -> [goto 1].
  • 2.2. If the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and -> [goto 1].
• 3. Found a match, then {return the index}.
• 4. Did not found a match, then {return -1}.

Edge Cases

There are some edge cases we must be aware:

1. The element might not exist in the array

If the element does not exist in the array we must make sure that the search does not get out of bounds and consequently creating an exception because of it trying to access an invalid index.

2. The target value could be in the rightmost or left most side of the array

3. The target value could be the initial, middle element

4. Duplicate entries could exist in the array

Using this algorithm to deal with duplicates is not appropriate, but it will return the position for the first element that it finds.

Implementation of the Binary Search algorithm using an iterative approach

	static int IterativeBinarySearch(int[] array, int target)
	{
	//Initialize the state of the indexes that correspond to the first and last available indexes in the array.
	var mostRightIndex = array.Length - 1;
	var mostLeftIndex = 0;
	// Iterate through the elements while the indexes are within the possible range
	while (mostLeftIndex <= mostRightIndex)
	{
	//Get the middle position of the array
	var middleIndex = mostLeftIndex + (mostRightIndex - mostLeftIndex) / 2;
	//Test if the middle element is the target value (best case scenario)
	if (array[middleIndex] == target) return middleElem;
	//Is our target to the left of the current element
	if (target > array[middleIndex])
	{
	//Because the element is of the left we want the sub-array on the left.
	//The firstElement is the same (0) but the last element is on the position before the middle element.
	//The middle element is excluded because we already checked if it was our target value and it can be discarded.
	mostLeftIndex = middleIndex + 1;
	continue;
	}
	//Because the element is on the right we want the sub-array on the right.
	//The lastElement is the same, but the firstElement is now the one whose position is after the middle element.
	//The middle element is excluded because we already checked if it was our target value and it can be discarded.
	mostRightIndex = middleIndex - 1;
	}
	//If the last element position is zero or less it means that the element was not
	//found or that the array as no values, so we can return -1 to indicate a negative match for the
	//target value
	return -1;
	}

view raw binary-search-iterative.cs hosted with ❤ by GitHub

Implementation of the Binary Search algorithm using a recursive approach

I find this approach the most natural when I start to write this algorithm. It doesn't make it better or worse than the iterative version.

	int RecursiveBinarySearch(int[] array, int target, int? mostLeftIndex = null, int? mostRightIndex = null)
	{
	//Initialize the state of the indexes that correspond to the first and last available indexes in the array or sub-array.
	if (!mostLeftIndex.HasValue) mostLeftIndex = 0;
	if (!mostRightIndex.HasValue) mostRightIndex = array.Length - 1;
	//If one of the indexes is in a situation like 0 < -1 or n < (n - 1) that means
	//the array does not contain the target value
	if (mostRightIndex < mostLeftIndex) return -1;
	//Get the middle position of the array
	var middleIndex = (int) (mostLeftIndex + (mostRightIndex-mostLeftIndex) / 2);
	//Test if the middle element is the target value (best case scenario)
	if (array[middleIndex] == target)
	{
	return middleIndex;
	}
	//Is our target to the right or to the left of the current element
	return target < array[middleIndex]
	//The target is smaller than the current element, then the target value must be on the left
	? RecursiveBinarySearch(array, target, mostLeftIndex, middleIndex - 1)
	//The target value is bigger than the current element, then the target value must be on the right
	: RecursiveBinarySearch(array, target, middleIndex + 1, mostRightIndex);
	}

view raw recursive-binary-search.cs hosted with ❤ by GitHub

Generic implementation of the binary search algorithm in C#

This algorithm is not necessarily used to only sort integers or numbers. You can use it to sort anything as long you can provide a way for the computer to know how to classify different objects. To see that in action, you can see this fiddle.

For this, you can use different strategies:

• The generic type you are using implements an IComparable and/or IEquatable.
• Add parameter to the method that executes the algorithm and passes a IComparison parameter.
• Add parameter to the method that executes the algorithm and passes a ICompararer parameter.

Explore the code

I have added the code in this fiddle, so you can test the variations and play with the code at will to make it easier to understand the concepts.