Introduction to Algorithms: Binary Search
Algorithms are the building blocks of every software solution. An engineer must have a firm grasp on their implementations to produce succinct, efficient, and scalable code.
The first algorithm we will be discussing, as the title suggests, is binary search.
Searching for an element in an array is a simple process, but as the size of the data set you are searching increases, so does the run time. Mitigating the effects of the growth in data size on your algorithm’s run time is the key factor you must consider when choosing which algorithm you will utilize to reach an intended result.
Let us consider the sorted array:
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };If we wanted to find the index location of a target value x, we could loop through each element, comparing the value at each index to x. Let’s define a method, and for this example our method will return the position of x in the array, and -1 if x is not found.
public static int Search(int[] sortedArray, int x)
{
for (int i = 0; i < sortedArray.Length; i++)
{
if (sortedArray[i] == x)
{
return i;
}
}
return -1;
}This approach will return us the index position as intended. For small data sets this approach works fine; however, how will its run time scale as the size of the data set, our sorted array in this case, increases?
If we denote the size of our data set as n, and we consider the worst case, our number not being found in the data set provided, we see that this loop will have to run n times to return a value. We say that this function has a O(n) time complexity, where the run time will scale linearly, as the size of n increases. For large data sets this is less than optimal. Like every problem in programming, there are many paths that lead to each solution, but not all of these paths scale efficiently.
To reach our solution quicker we can use binary search. This algorithm has a time complexity of O(log n), or rather run time scales in proportion to the logarithm of the input size. The main premise of binary search is to cut the search array in half each iteration, by comparing our target value to the element at the midpoint of the search array. If our target value is greater than the value at the midpoint, we should then discard the left half of our array we are searching and search only the right half. If our target value is less than the value at the midpoint, we should discard the right half and search only the left. We perform this comparison until we find our target value, or the array that we are searching has a size 0. In this example, let’s follow the iterative design approach for the algorithm.
public static int BinarySearch(int[] sortedArray, int x)
{
int high = sortedArray.Length - 1;
int mid;
int low = 0; while (low <= high)
{
mid = (low + high) / 2;
if (sortedArray[mid] < x)
{
low = mid + 1;
}
else if (sortedArray[mid] > x)
{
high = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
As described above, our new method finds the midpoint of our sorted array, and each iteration cuts the domain of our search in half. This method returns the same value as our previous example, but gets to this return value much more efficiently in the case of large input size.
Consider the following programmatic situation:
Integer array rotatedArr is a sorted array that has been rotated, or manipulated such that it’s first element has been moved to the end of the array an unknown amount of times. Use a modified binary search to find if the target value x is present within the array, and if so return the index position it was found at.
int[] rotatedArr = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };— — — — — — — — — — — —ANSWER— — — — — — — — — — —
Stumped? Take it step by step to build out a solution using this new algorithm.
If you take a closer look at the rotated array, you may notice that one half of the array split at the middle is in sorted order, and the other is not. Keep this in mind moving forward. The basic structure of the search is the same, but by implementing logic that uses the previously mentioned property of the array, you account for the fact that rotatedArr is not provided in sorted order, and preserve the time complexity of the algorithm.
public static int RotatedBinarySearch(int[] rotatedArray, int x)
{
int high = rotatedArray.Length - 1;
int mid;
int low = 0; while (low <= high)
{
// new logic
}}
The high, mid, and low assignments stay the same from the last method, as you still need these references to get the cut-search-array-in-half behavior that is fundamental to binary search. The while loop also stays the same as it ends when the sub array you are searching has size 0.
public static int RotatedBinarySearch(int[] rotatedArray, int x)
{
int high = rotatedArray.Length - 1;
int mid;
int low = 0; while (low <= high)
{
mid = (low + high) / 2;
if (rotatedArray[mid] == x)
{
return mid;
}
else if (rotatedArray[mid] >= rotatedArray[low])
{
if (x > rotatedArray[low] && x < rotatedArray[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
else
{
if (x > rotatedArray[mid] && x <= rotatedArray[high])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
}
return -1;
}
Take time to examine the new logic. You now have built conditionals that check if the sub arrays to each side of the mid are sorted. You then try to find the target value x within the sorted sub array. If x is not present, you direct your search to the other half of the search array, and restart your process from there.
This solution demonstrates the benefits of binary search, and its ability to evolve solve more complex search problems while keeping time complexity logarithmic.
