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
- 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
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.
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.
Top comments (0)