In a binary search, we have two comparisons one for greater than and other for less than, otherwise its the mid value. How would you optimize so that we need to check only once?

```
bool binSearch(int array[], int key, int left, int right)
{
mid = left + (right-left)/2;
if (key < array[mid])
return binSearch(array, key, left, mid-1);
else if (key > array[mid])
return binSearch(array, key, mid+1, right);
else if (key == array[mid])
return TRUE; // Found
return FALSE; // Not Found
}
```

If you want to optimize your binary search algorithm you must replace recursion with iteration. See examples at wikipedia.

Let me know if you need more details.

For integers it doesn't matter, don't do it.

For more expensive comparisons use -1, 0, 1 for <, =, > like in the C library function strcmp or Java's compareTo().

It's not advisable to try and optimize in the way you describe. From the Binary Search Algorithm article on Wikipedia:

About half the time, the first test will be true so that there will be only one comparison of a and b, but the other half of the time it will be false, and a second comparison forced. This is so grievous that some versions are recast so as not to make a second test at all thus not determining equality until the span has been reduced to zero, and thereby foregoing the possibility of early termination – remember that about half the time the search will happen on a matching value one iteration short of the limit.

It is quite easy to make this problem still worse (e.g. as in [3]) by using an order such as

```
if a = b then action3
else if a > b then action2
else action1;
```

Rather than detecting equality early (as it might appear to), this will force two comparisons to be performed for all but the last iteration of a search.

Some languages, like Fortran, have a three-way comparison that allows this step to be done with one comparison that branches to three different sections (see the tenth line of the Three-way comparison example). If your language doesn't support a three-way test (most languages don't) then two comparisons is the best you can do.

I *would* advise you to check out the iterative implementation from the same article, though.

In the code you posted, you can remove the last comparison. That is, if `key`

is not less than `array[mid]`

or greater than `array[mid]`

, then by definition it's equal. So your code becomes:

```
mid = left + (right-left)/2;
if (key < array[mid])
return binSearch(array, key, left, mid-1);
else if (key > array[mid])
return binSearch(array, key, mid+1, right);
else
return TRUE; // Found
```

Also note that I've removed the last line. In your original code, it's impossible for the `return FALSE;`

ever to be executed. I would assume that you have a check at the beginning of your `binSearch`

which checks to see if `left`

<= `right`

.

In C, there is no way to do a three-way comparison/branch based on less than, equal, greater than, so you have to do two comparisons to select among three possibilities.

I would try the bsearch() standard function first. Chances are good that it performes better than your approach.

Ganesh M - If the key does not exist in the array, then your function will be stuck inside of a never ending loop. It can never return FALSE.

What is the optimal way to find the insertion point, if the key does not exist?

A conditional "if cascade" accounting for <, ==, and > will only return TRUE, or continue to compute forever.

I need the optimal condition to determine when a key has been isolated as not existing.

I know that this will slow down the search, but I want to slow it down by the least amount.

playing with log(N)/log(2) seems like a good idea, but when N is not a power of 2, things can go haywire.

Perhaps, I should choose an array with a size of power of 2, and use a simple while loop?

does checking if the midpoint == to either bound increase the number of comparisons too much?

I tried to reconstruct the optimization steps of the binary search algorithm. I start with this iterative version:

```
int binsearch_1( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
int found=0;
while( size > 0 ){
size_t w=size/2;
if( p[w] < key ){ p+=w+1; size-=w+1; }
else if( p[w] > key ){ size =w; }
else /* p[w] == key */{ p+=w; found=1; break; }
}
*index=p-array; return found;
}
```

Eliminating comparisons from the loop:

```
int binsearch_2( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
while( size > 0 ){
size_t w=size/2;
if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else size =w;
}
*index=p-array; return p[0]==key;
}
```

Unrolling small sizes from the loop:

```
int binsearch_3( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
while( size > 8 ){
size_t w=size/2;
if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else size =w;
}
if( size==8 ){ if( p[5] <= key ){ p+=5; size=3; } else size=4; }
if( size==7 ){ if( p[4] <= key ){ p+=4; size=3; } else size=3; }
if( size==6 ){ if( p[4] <= key ){ p+=4; size=2; } else size=3; }
if( size==5 ){ if( p[3] <= key ){ p+=3; size=2; } else size=2; }
if( size==4 ){ if( p[3] <= key ){ p+=3; size=1; } else size=2; }
if( size==3 ){ if( p[2] <= key ){ p+=2; size=1; } else size=1; }
if( size==2 ){ if( p[2] <= key ){ p+=2; size=0; } else size=1; }
if( size==1 ){ if( p[1] <= key ){ p+=1; } }
*index=p-array; return p[0]==key;
}
```

Reordering if statements, moving special cases [size==pow(2,N)-1] to the end:

```
int binsearch_4( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
while( size > 8 ){
size_t w=size/2;
if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else size =w;
}
if( size==8 ){ if( p[5] <= key ){ p+=5; size=3; } else size=4; }
if( size==6 ){ if( p[4] <= key ){ p+=4; size=2; } else size=3; }
if( size==5 ){ if( p[3] <= key ){ p+=3; size=2; } else size=2; }
if( size==4 ){ if( p[3] <= key ){ p+=3; size=1; } else size=2; }
if( size==2 ){ if( p[2] <= key ){ p+=2; size=0; } else size=1; }
if( size==7 ){ if( p[4] <= key ){ p+=4; size=3; } else size=3; }
if( size==3 ){ if( p[2] <= key ){ p+=2; size=1; } else size=1; }
if( size==1 ){ if( p[1] <= key ){ p+=1; } }
*index=p-array; return p[0]==key;
}
```

Changing if statements to a switch statement:

```
int binsearch_5( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
while( size > 8 ){
size_t w=size/2;
if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else size =w;
}
if( size==8 ){ if( p[5] <= key ){ p+=5; size=3; } else size=4; }
if( size==6 ){ if( p[4] <= key ){ p+=4; size=2; } else size=3; }
if( size==5 ){ if( p[3] <= key ){ p+=3; size=2; } else size=2; }
if( size==4 ){ if( p[3] <= key ){ p+=3; size=1; } else size=2; }
if( size==2 ){ if( p[2] <= key ){ p+=2; size=0; } else size=1; }
switch(size){
case 7: if( p[4] <= key ) p+=4;
case 3: if( p[2] <= key ) p+=2;
case 1: if( p[1] <= key ) p+=1;
}
*index=p-array; return p[0]==key;
}
```

Extending switch statement to handle all of the special cases:

```
int binsearch_6( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
switch( size ){
#define C(n) case ((size_t)1<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1);
#if SIZE_MAX == UINT64_MAX
C(63) C(62) C(61)
C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif
C(31)
C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C
break;
default:
while( size > 0 ){
size_t w=size/2;
if( p[w] < key ){ p+=w+1; size-=w+1; } else size=w;
}
}
*index=p-array; return p[0]==key;
}
```

Eliminating the general case handling from the code: [ w is the smallest number: w==pow(2,N)-1; size<=2*(w+1) ]

```
int binsearch_7( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
size_t w=(size-1)>>1; w|=w>>1; w|=w>>2; w|=w>>4; w|=w>>8; w|=w>>16;
#if SIZE_MAX == UINT64_MAX
w|=w>>32;
#endif
if( p[w]<key ) p+=size-w-1;
switch( w ){
#define C(n) case ((size_t)1<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1);
#if SIZE_MAX == UINT64_MAX
C(63) C(62) C(61)
C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif
C(31)
C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C
}
*index=p-array; return p[0]==key;
}
```

The last step what i made was the simplifying of the case labels [from: '((size_t)1<<n)-1' to: 'n'] but i found that the modified code was slower on my old PC than the previous version.

```
// Optimized Binary Search Implementation
int binsearch(int* data, int size, int val)
{
int result = -1;
int start, mid, end;
start = 0;
end = size - 1;
mid = (start + end) >> 1;
while (start <= end && data[mid] != val)
{
if (data[mid] > val)
end = mid - 1;
else
start = mid + 1;
mid = (start + end) >> 1;
}
if (val == data[mid])
result = mid;
return result;
}
```

Its an exercise question in K&R second edition.

```
While(low <= high && arr[mid]!=num)
{
if(arr[mid] > num)
{
low = mid+1;
}
else
{
high = mid-1;
}
mid = (low+high)/2;
}
if(arr[mid] == num)
{
printf("found the ugly number");
return mid;
}
```

```
BinarySearch = function (array, value)
{
var l = 0;
var r = array.length;
var mid;
while (l!=r)
{
mid = Math.round( (r+l)/2 )-1;
if(value > array[mid])
l=mid+1;
else
r=mid;
}
if(array[mid]==value)
return mid;
else
{
if( (mid < (array.length-1)) && (array[mid+1]==value) )
return mid+1;
else
return -1; // Not found
}
}
```

source: http://calcs.appspot.com/docview?id=agVjYWxjc3IPCxIIRG9jdW1lbnQY0w8M

```
bool binSearch(int array[], int key, int len)
{
int mid, low, high;
low = 0;
right = len - 1;
mid = low + (high-low)/2;
while ((low <= high) && (array[mid] != key)) {
if (key < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
mid = low + (high-low)/2;
}
if (array[mid] == key) {
return TRUE;
}
return FALSE;
}
```

Similar Questions

What is the difference between binary search and binary search tree? Are they the same? reading the internet it seams the second is only for trees(up to 2 children nodes) and binary search doesn't fol

I'm trying to make a breadth first search function for a binary search tree, but I don't seem to be able to make it work. Any pointers would be greatly appreciated! template <class T> bool BST&l

I have seen many example of binary search,many method how to optimize it,so yesterday my lecturer write code (in this code let us assume that first index starts from 1 and last one is N,so that N is l

I'm getting a problem with my display functions dealing with binary search trees. The main problem I'm having is getting the count variable to increment correctly in the recursive function so that I c

I want to write a simple binary reconstruction algoithm in matlab. So far I know this algorithm is used after 'opening' to grow back pieces of the original image that are connected to the opening. I'v

http://en.wikipedia.org/wiki/Binary_search_algorithm#Average_performance BinarySearch(int A[], int value, int low, int high) { int mid; if (high < low) return -1; mid = (low + high) / 2; if (A[mid]

//Binary search using c++. The main function does not give any output. This is simple binary search algorithm implementation. #include <iostream> using namespace std; int BinarySearch(int *a, in

I run the following code which is Insertion Sort algorithm that use binary search to find the right position of the item being inserted instead of linear search but there are two numbers in the result

How does the search algorithm on stackoverflow work? I need to implement a search functionality in one of my web sites.

I've found the following code online, int binary_search(int a[], int low, int high, int target) { if (high < low) return -1; int middle = (low + high)/2; if (target < a[middle]) return binary_s

I need to build a balanced binary search tree. So far my program inserts the numbers from 1 to 26, but my program does not build it into a balanced binary search tree. If anyone could look at my code

I need a function for 'smart' search which will return number of elements in binary tree which are greater then given parameter but wont go through all nodes. For example, if i want to find number of

I had a question of exactly how a binary search tree of strings works. I know and have implemented binary search trees of integers by checking if the new data <= parent data then by branching left

i am doing jump search algorithm but it show me that element is not in array while it is here is code import java.math.*; public class jamp { public static int min(int a,int b) { return a<b?a:b; }

I need an algorithm for returning the successor node of some arbitrary node of the given binary search tree.

I want to create a PHP recursive program using a Binary Tree and Recursion. I want to print the binary tree level by level using recursion. I want to recurse through the tree, push the node into a has

Write a bash script to do a binary search. Read student names and grades from a file into an array. Prompt the user for a student name. Find the name in the array and display the grade. The data in th

Is it possible to optimize this kind of (matrix) algorithm: // | case 1 | case 2 | case 3 | // ------|--------|--------|--------| // | | | | // case a| a1 | a2 | a3 | // | | | | // case b| b1 | b2 | b

I need a script to search efficiently all the duplicates in a one-dimensional array. I tried a naive method : for(var i=0, ii<arr.length-1; i<ii; i++) for(var j=i+1, jj<arr.length; j<jj; j

I am reading Section 9.3 of Jon Bentley's Programming Pearls, 2nd Edition. On page 94, Jon gave an implementation of an improved binary search algorithm, utilizing the fact that n is 1000 (search 1000

I'm looking for an algorithm to find the first number less than X in an array of integers. Actually I'm using linear search,but I think that binary search may be better(as I already have seen sometime

How much does it cost the search operation in a Binary tree? Is it O(n)?

The problem is to extend the binary search algorithm to find all occurrences of a target value in a sorted array in the most efficient way. Concretely speaking, the input of the algorithm are (1) a so

Suppose an array has been given and want to find element in that array , how can you search an element in that array using binary search and that given array is already sorted and size of the array is

I want to make my own binary search algorithm to search ArrayList of 1 000 000 elements. I decided to do the search with do-while loop. I am aware I could use while() loop. But when I run it, it takes

Below is an iterative algorithm to traverse a Binary Search Tree in in-order fashion (first left child , then the parent , finally right child) without using a Stack : (Idea : the whole idea is to fin

I am trying to implement a binary search in Java, doesn't work... don't know why, It always gives me an error saying the number wasn't found... I am not sure why, I'm not seeing any error :S thanks fo

I can not figure out why this will not return the key, it seems to be skipping over the step, the logic i feel is straight, if midptr is less than key then search right else search left side. but its

Which is better (space/time) to find certain strings: To use a vector of strings (alphabetically ordered) and a binary search. To use a BST of strings (also ordered alphabetically). Or are both simi

I need help with implementing the binary search algorithm, can someone tell me what's wrong with my code: public int bsearch(Item idToSearch) { int lowerBoundary = 0; int upperBoundary = myStore.size(

Ok, I am trying to get a binary search tree to balance, and I know why it's not working, but I don't know how to fix it. This is what I have for my balancing methods. public void balance(){ if(isEmpt

After having searched the internet I was not able to satisfy myself that I had found a comprehensive set of situations in which a linear search would be preferable to a binary search. I am essentiall

Im a little confused. Im wondering if an array based Binary Search tree is implemented this way? void BST::insert(item &items, const data & aData ) {//helper function. Parent++; data *new_data

I have this array (A) with n elements that are guaranteed to be sorted and I need to perform a binary search on them in a parallel system. I started off by making this binary search algorithm. It's it

Im trying to build an array based, Binary Search Tree by following the algorithm at: http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif%3A:600%3A:388%3A%3A/sites/dl/free/0070131511/2532

Can the performance of this sequential search algorithm (taken from The Practice of Programming) be improved using any of C's native utilities, e.g. if I set the i variable to be a register variable ?

using a binary search tree I need to add to a vector all int elements of the heaviest path of the tree. for example I have 20,7,6,9,11,21 the values that should be added to the vector would be 20 ,7,9

I am trying to write a program that takes in strings and places them in a binary search tree in alphabetical order once these are inserted into the tree, a user prompts for one word to be deleted, thu

I was reading an algorithms book which had the following algorithm for binary search: public class BinSearch { static int search ( int [ ] A, int K ) { int l = 0 ; int u = A. length −1; int m; while (

How do I add say 1000, 10000, 1000000, or 10000000 individual data items to a search algorithm? Code: public class BinarySearch { int binarySearch(int[] array, int value, int left, int right) { if (l

I am writing a program that reads in a student record if you will and then separates it into 4 binary search trees based on the data. I am attempting to delete a node, but instead of actually removi

I am reading through the binary tree delete node algorithm used in the book Data Structures and Algorithms: Annotated Reference with Examples on page 34 , case 4(Delete node which has both right and l

Simple question - given an IList<T> how do you perform a binary search without writing the method yourself and without copying the data to a type with build-in binary search support. My current

I have a book that explains the theory behind binary search tree in a very bad way i know that there is something about the order of both left and right child but i still cannot get the idea about one

Well i build a basic Binary Search Tree using a class called Node for simplicity i will include the core method that is used to insert Nodes public function addNode($node) { if ($this->left == null

I am writing a prototype of a new app for an enterprise. I want to include a great search engine, which is something they have never had before. What I am looking for is something that can translate a

I'm working on a programming assignment and writing a bunch of functions to implement a binary search tree, and some functions are given. I thought I understood recursion, but I keep getting hung up o

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove mathe

I am working on a Binary Tree program for school and I have everything working perfectly. All I am working on now is the proper output. My teacher wants the output to be all the numbers in sorted orde

So, the question is to find the largest sub-tree (the largest sub-tree is the node with maximum size) in a binary tree which is a BST. I found the following website which enlists an algorithm. http://