**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:**

`log n`

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