ZeroReverseSoft

programming and stuff

Algorithms: Binary search explanation and C# implementation

Posted by zeroreverse on 07/02/2013

prog
Binary search is one of the most basic yet very useful algorithms. It can operate on sorted arrays or range of values. Some people consider it divide and conquer algorithm, others don`t, but it does not really matter. The goal of binary search is to find a specified value (or its index) within an array or a range of values, it can also be used to search for a unknown value which must meet certain known conditions.

Algorithm Overview
So what does binary search do – it defines start, end and middle points for the sorted array or range in which it will be performing a search. On each iteration, depending on how the value at the middle point compares to the value we are searching for, it redefines the start or end point and subsequently the middle point. This way the size of the array or range we are searching in is effectively halved every iteration until we find what we search for or the exit conditions are met before that (we have found nothing). The exit condition is start point > end point.

Example
So, before looking at the pseudo code and C# implementation, lets first look at an example.

We have the sorted array arr:
ArrFullWe want to search for the number 1337 in this array.

  • Step 1 :
    The start point is at i=0, the end point is at i=6. The middle point is at i=(start+end)/2=3. So we have start=0, end=6 and mid = 3. Lets compare the value at the middle of the array to the one we are searching for – arr[mid]=666, 666<1337, what this means is that if 1337 exists in this sorted array, since it is higher than the value at the current middle point it must be located to the right, relative to it. So we don`t care about whats to the left and adjust the starting point accordingly => start=mid+1
  • Step 2:
    Having modified the start point, the array on which we will be performing a search looks like this:
    Arr2
    We see that start=4, end=6 and mid=5Again we compare the value at the mid to the one we are searching – arr[mid]=1111, 1111<1337, once more it looks like if the value we search for exists it would be located to the right of the current mid point, we modify the start point => start=mid+1
  • Step 3:
    arr3
    The new starting point is at 6,  the end point too is at index 6, that means the the middle will also be located at index 6. arr[mid]=1337, 1337==1337 wohoo :D we have found it and its located at index 6. At this point the algorithm should returns the index and exit.

Pseudocode
At this point you should have general understanding of how the binary search algorithm works. But here is a simple pseudocode to clear things up (*wwsf=”what we are searching for”):

while(start<=end)
	mid=(start+end)/2
	if(arr[mid]<wwsf)
		start=mid+1
		continue
	if(arr[mid]>wwsf)
		end=mid-1
		continue
	if(arr[mid]==wwsf)
		return mid
return not_found

C# Implementation
Its nothing special really, by now, even if you are a novice, you can probably do it yourself. Some people like to use recursion, I hate it (really really hate it), so no recursion here:

public static int BinarySearch(int[] arr, int lowBound, int highBound, int value)
    {
        int mid;
        while (lowBound <= highBound)
        {
            mid = (lowBound + highBound) / 2;
            if (arr[mid]<value)//the element we search is located to the right from the mid point
            {
                lowBound = mid + 1;
                continue;
            }
            else if (arr[mid] > value)//the element we search is located to the left from the mid point
            {
                highBound = mid - 1;
                continue;
            }
            //at this point low and high bound are equal and we have found the element or
            //arr[mid] is just equal to the value => we have found the searched element
            else 
            {
                return mid;
            }
        }
        return -1;//value not found
    }

So that`s about it. Its a really easy algorithm and as far as i remember it was the first one I was able to implement by myself, back when I was just a scrubling. If you ever happen to stumble on this post and have a question, feel free to ask in the comments, I will be happy to help if I can.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: