Efficient Binary Search

Edit :
Here I have proposed 3 modified binary search functions namely mod_bsearch1(), mod_bsearch2() and mod_bsearch3().
Out of these 3, mod_bsearch3() is most efficient so please use mod_bsearch3() for benchmarking purposes.

Binary search is way more efficient than linear search.
The traditional binary search is generally coded as follows:

bool bsearch(int array[], int size, int *loc, int val)
{
	int first, mid, last;
	int count;

	first = 0;
	last = size - 1;
	count = 0;

	while(first <= last)	//Unless first and last crosses each other
	{
		printf("Pass %d\n", ++count);
		mid = first + (last - first)/2;
		
		if (val == array[mid])
		{
			*loc = mid;
			return true;
		}
		else if (val < array[mid])
			last = mid - 1;
		else
			first = mid + 1;
	}
	
	return false;
}

Now what if val < array[first] or array[last] < val in any pass ?
If any of the above tests is true then clearly element is NOT in the given list. There is absolutely no point in searching till last crosses first.

So let’s code the modified binary search:

1) mod_bsearch1()

bool mod_bsearch1(int array[], int size, int *loc, int val)
{
	int first, mid, last;
	int count;

	first = 0;
	last = size - 1;
	count = 0;

	while(array[first] <= val && val <= array[last])
	{
		printf("Pass %d\n", ++count);
		mid = first + (last - first)/2;

		if (val == array[mid])
		{
			*loc = mid;
			return true;
		}
		else if (val < array[mid])
			last = mid - 1;
		else
			first = mid + 1;
	}
	
	return false;
}

To our surprise this modified code is more efficient that the traditional one. Let’s check the performances of both the codes.

main() can be coded as follows :

#include <stdio.h>
#include <stdbool.h>

#define SIZE 10

bool bsearch(int [], int , int *, int);
bool mod_bsearch1(int [], int , int *, int);

int main(void)
{
	int loc, val, i;
	int array[SIZE];
	
	printf("Enter 10 elements : ");
	for(i = 0; i < SIZE; i++)
	scanf("%d", &array[i]);
	
	printf("Element to be searched : ");
	scanf("%d", &val);
	
	printf("\nTraditional Binary Search: \n");
	if(bsearch(array, SIZE, &loc, val))
		printf("%d was found at location : %d\n", val, loc);
	else
		printf("%d was Not Found!\n", val);
	
	printf("\nModified Binary Search: \n");
	if(mod_bsearch1(array, SIZE, &loc, val))
		printf("%d was found at location : %d\n", val, loc);
	else
		printf("%d was Not Found!\n", val);

	return 0;
}


$ gcc binary.c -o binary
$ ./binary
Enter 10 elements : 2 4 6 8 10 12 14 16 18 20
Element to be searched : 9

Traditional Binary Search:
Pass 1
Pass 2
Pass 3
Pass 4
9 was Not Found!

Modified Binary Search:
Pass 1
9 was Not Found!

Wow! Traditional binary search took 4 passes to know 9 isn’t there in given array whereas the modified version took just 1 pass. That’s pretty impressive! But how did it happen ? And is modified binary search always more efficient than traditional binary search ?
Let’s find out.

Analysis:
Now let’s compare the traditional binary search function (bsearch()) and modified binary search function (mod_bsearch()).
It’s clear that if an element to be searched is in a given array then no. of passes in traditional binary search and modified binary search will be same as modified version alters the logic of traditional binary search only if element to be searched falls outside the bounds.
Now what if element to be searched is NOT in a given array ?
For that purpose let’s consider the worst cases:
1) array of 1 element and
2) array of 2 elements
as every other array falls to these two sub arrays eventually (if element is not found till the end).

Case 1: Array of 1 element
In traditional binary search this 1 element array constitutes 1 pass. At the end of this pass either first = last + 1 or last = first - 1 as we have assumed that element is NOT in an array. Hence there is no next pass as at the end of this pass first and last crossed each other.
But in modified binary search there is no separate pass for this 1 element array as at the while statement itself it’s clear that element is not in this array.
So, if binary search continues till 1 element array then in that case modified binary search function yields 1 less pass than traditional binary search function.

Case 2: Array of 2 elements
In traditional binary search function the sub array of 2 elements will require 1 pass. At the end of the pass either val < array[mid] or val > array[mid] as we have assumed that element is NOT in an array.
If val < array[mid] then last = first - 1 as for 2 elements array mid = first . So there will be NO next pass. This current single pass only.
But if val < array[mid] then this pass itself will not be there in modified binary search as mid = first here. So modified binary search again will save 1 pass here.
Now if val > array[mid] then this will lead to 1 element array in which case modified binary search saves 1 pass than traditional binary search (case 1).

Conclusions:

  • Complexity of both the versions is log n.
  • If element to be searched is present in a given array then the no. of passes for traditional binary search and modified one are same.
  • If element to be searched is NOT in a given array then no. of passes for modified binary search are at least 1 less than that of traditional version.
    So it can be safely said that modified binary search is more efficient than traditional binary search.

    P.S.
    In case you didn’t notice, in modified version we are checking both the conditions for trueness which is NOT necessary from pass 2. We Just have to check corresponding single condition depending upon whether first was changed or last was changed in previous pass.
    This can be achieved using a flag variable as follows:

    2) mod_bsearch2()

    bool mod_bsearch2(int array[], int size, int *loc, int val)
    {
    	int first, mid, last;
    	int flag, count;
    	
    	first = 0;
    	last = size - 1;
    	count = 0;
    	
    	if(array[first] <= val && val <= array[last])
    	do
    	{
    		printf("Pass %d\n", ++count);
    		mid = first + (last - first)/2;
    		flag = 0;
    		
    		if (val == array[mid])
    		{	
    			*loc = mid;
    			return true;
    		}
    		else if (val < array[mid])
    		{
    			last = mid - 1;
    			flag = 1;
    		}
    		else
    			first = mid + 1;
    	}while(flag ? val <= array[last] : array[first] <= val);
    
    	return false;	
    }

    But here again we are evaluating two conditions in do while(expression). First one is flag and second one is val <= array[last] or array[first] <= val depending upon the value of flag .
    So this version can’t be said to be more efficient than earlier modified version i.e. mod_bsearch1().
    If anybody can think of a workaround then please let me know.

    Edit :
    I think I figured it out.

    3) mod_bsearch3()

    bool mod_bsearch3(int array[], int size, int *loc, int val)
    {
    	int first, mid, last;
    	int flag, count;
    	int less, more;
    	
    	first = 0;
    	last = size - 1;
    	count = 0;
    	
    	if(array[first] <= val && val <= array[last])
    	do
    	{
    		printf("Pass %d\n", ++count);
    		mid = first + (last - first)/2;
    		
    		if (val == array[mid])
    		{	
    			*loc = mid;
    			return true;
    		}
    		else if (val < array[mid])
    		{
    			last = mid - 1;
    			less = val;
    			more = array[last];
    		}
    		else
    		{
    			first = mid + 1;
    			less = array[first];
    			more = val;
    		}
    	}while(less <= more);
    
    	return false;	
    }

    About these ads
  • About rootkea

    Curious n00b
    This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

    3 Responses to Efficient Binary Search

    1. Brandon says:

      Don’t wait until the loop ends to evaluate the remaining condition; evaluate the remaining condition in each branch and if it evaluates to true, then continue.
      if (val == array[mid])
      {
      *loc = mid;
      return true;
      }
      else if (val < array[mid])
      {
      last = mid – 1;
      if (condition condition1) continue;
      }
      else
      {
      first = mid + 1;
      if (condition condition2) continue;
      }
      }

    2. rootkea says:

      Thanks for that trick Brandon!.
      I think this should work with do while(false);
      But I don’t think your trick solves the problem of having to evaluate two conditions in do while(expression); As in this case too we need to know whether the control reached at expression in do while(expression); has arrived through continue or not. If it has then we will start the next iteration and if not then we exit from the loop. So in this approach also we need to check if-else logic while evaluating the expression in do while(expression);
      Edit :
      Hey Brandon, I figured it out. Please check the post again.

    3. pratik says:

      great work avinash !!!

    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