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;	
    }

  • Posted in Uncategorized | Tagged , , , , , | 3 Comments

    NOT Been Fully Patched : Facebook Timeline Privacy Compromised

    On March 14, 2013 I got a new Facebook Timeline layout and while exploring it I noticed a glitch. I had set the visibility  of my ‘Other Likes’ to ‘Only me’. In spite of that I could see all of my ‘Other Likes’ while using the ‘View as Public’ tool.

    For more details Facebook Timeline Privacy Compromised

    Since I received the new Timeline update that day only, I thought the bug was in updated timeline code and hence considered it as a breach in Timeline privacy. Moreover none of my friends had the new Timeline layout so I couldn’t confirm whether the bug was in Timeline privacy or ‘View as’ tool.

    On March 20, 2013 Pranav Hiran commented with a screenshot indicating that the bug was in ‘View as’ tool and not in Timeline privacy. http://rootkea.quora.com/Facebook-Timeline-Privacy-Compromised/comment/185880

    And I also noticed that the bug was ‘apparently’ been fixed. Facebook Timeline Privacy Compromised

    Yes! Apparently!

    -30922fb9cf2e66a8

    The bug in ‘View as’ tool is STILL ALIVE for old Facebook Timeline accounts.

    Note: For the following description I am using my friend’s Facebook account which hasn’t got the new Timeline layout yet.

    As you can see in this screenshot I have set the visibility of ‘Other Pages You Like’ to ‘Only Me’.

    Now when I try to view my profile (my friend’s actually) using ‘View as Public’ tool I am still able to see all of my ‘Other Pages’ even if I have set the privacy for ‘Other Pages’ to ‘Only Me’.

    But if I try to view his profile from my account I am unable to see ‘Other Pages’ as their visibility is being set to ‘Only Me’ by that’s him. The account holder.

    So clearly the bug lies in ‘View as’ tool which has been fixed for new Timeline accounts but NOT for the old Timeline accounts.

    I hope FB guys fill this hole soon and that’s too completely! ;)

    Posted in Uncategorized | Tagged , , | Leave a comment

    while(1) printf(“Something’s wrong with FB News Feed! \n”);

    Few days ago I encountered a bug in ‘updated’ Facebook Timeline. It’s to be confirmed whether the bug is in ‘View as’ feature only or indeed the Timeline privacy is confirmed since I couldn’t find the volunteer with new timeline layout account.
    For more details click here. https://rootkea.quora.com/Facebook-Timeline-Privacy-Compromised
    I reported it too Facebook too but still the bug is not fixed.

    Screenshot 4
    Any ways here goes another one.
    This time it’s Facebook News Feed. Sometimes News Feed just behaves in a weird manner. It simply goes in never-ending loop. I first noticed this bug 2 months ago but then I didn’t think of it being serious and didn’t record it. Then again after a month or so (More precisely on February 5 2013) I again noticed the glitch and I recorded it. But there was a problem with that video. It was exposing handful of my personal details so I didn’t post it. I tried to edit that video but nothing worked on Ubuntu. I tried well-known editors like Openshot , Pitivi but none did the job. Since I didn’t want to work on Windows machine that video still resides in my Videos directory. :D

    Finally today I experienced the same bug. I quickly recorded it with Kazam Screencaster. I was about to post it and suddenly I noticed the Greasemonkey icon there. Though I didn’t have any userscript installed but I decided to uninstall the Greasemonkey and rerecord the video to avoid any doubt about the video being genuine and hence the bug. Right now I have ‘Unfriend Finder’ addon installed in Mozilla Firefox which has nothing to do with Facebook News Feed as the previously mentioned video (the one which exposes too many personal details) which was shot a month ago didn’t have the ‘Unfriend Finder’ installed in Firefox. Though I have posted that February 5 video on Youtube as ‘private’,  I’ll provide it to Facebook employee if they ask.

    And finally here goes the video.

    Sometimes Kazam kind of hangs. The credits for last few seconds (about 20-30) all goes to this crazy thing with Kazam. ;)

    Posted in Uncategorized | Tagged , | Leave a comment

    Hello world!

    Welcome to WordPress.com! This is your very first post. Click the Edit link to modify or delete it, or start a new post. If you like, use this post to tell readers why you started this blog and what you plan to do with it.

    Happy blogging!

    Posted in Uncategorized | 1 Comment