NMKN Studio

We've looked at the linear search algorithm before (here), today we're looking at an improvement to this brute force method- binary search algorithm. This will only work on a sorted array. 

This algorithm is going to check the value in the middle of the array and compare it to the value we're searching for. It'll check if the value searched for is equal, lesser or greater than the value at the midpoint. If it is equal, then the story ends here since we found the match. If it's lesser than the value at the midpoint, we'll going to narrow the search field to only include the values below that mid point. If it's greater, then we're going to narrow the search field to only include the values above that midpoint. Once it's done checking it'll return the index which contains the value of interest. Here's how it'd look like coded:

		int midPoint = (lowerBound + upperBound) / 2;

		if (val == arr[midPoint])
		{
			return midPoint;
		}
		else if (val > arr[midPoint])
		{

			lowerBound = midPoint + 1;

		}
		else if (val < arr[midPoint])
		{
			upperBound = midPoint - 1;
		}

Note: Good thing to do is to create a piece of code first and then create a loop for it if it needs to be running repeatedly. This way you'll be able to see more clearly what type of a loop to use and how to configure it.

So the midpoint is of course the point between the lower and upper boundaries of the current portion of the array we're currently looking at. We'll need to enclose it within a loop of some sort though to carry on checking until we found the index. We can see from the breakdown below that the boundaries slowly close in on each other:

Download File

Therefore we could make use of this observation and create the following condition for the loop:

	while (lowerBound <= upperBound)
	{

		int midPoint = (lowerBound + upperBound) / 2;

		if (val == arr[midPoint])
		{
			return midPoint;
		}
		else if (val > arr[midPoint])
		{

			lowerBound = midPoint + 1;

		}
		else if (val < arr[midPoint])
		{
			upperBound = midPoint - 1;
		}

	}

The whole function looks like this:

int binarySearch(int arr[], int val, int size)
{

	int lowerBound=0;
	int upperBound=size-1;

	while (lowerBound <= upperBound)
	{

		int midPoint = (lowerBound + upperBound) / 2;

		if (val == arr[midPoint])
		{
			return midPoint;
		}
		else if (val > arr[midPoint])
		{

			lowerBound = midPoint + 1;

		}
		else if (val < arr[midPoint])
		{
			upperBound = midPoint - 1;
		}

	}

}

Upper bound variable is equal to the size of the array minus one, because the indexes are numbered 0 to n, where n is the highest index of the array. Size is equal to how many elements are in the array, hence we need to subtract 1 from it.
Below you can find the enrite program:

#include <iostream>
using namespace std;

int binarySearch(int arr[], int val, int size)
{

	int lowerBound=0;
	int upperBound=size-1;

	while (lowerBound <= upperBound)
	{

		int midPoint = (lowerBound + upperBound) / 2;

		if (val == arr[midPoint])
		{
			return midPoint;
		}
		else if (val > arr[midPoint])
		{

			lowerBound = midPoint + 1;

		}
		else if (val < arr[midPoint])
		{
			upperBound = midPoint - 1;
		}

	}

}

int main()
{

	int arr1[] = { 12,22,34,47,55,67,82,98 };
	int val1 = 67;
	int size = sizeof(arr1) / sizeof(arr1[0]);

	int returnedIndex;

	std::cout << size << std::endl;
	std::cout << 11/2 << std::endl;

	returnedIndex = binarySearch(arr1, val1, size);

	std::cout << returnedIndex << std::endl;

	return 0;
}

And there you have it!

HYPER!locrian