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

I have many arrays with sorted data. I need to perform binary search in this arrays. If key ranges in this arrays were disjoint it will be possible to sort arrays by range and then perform binary sear

I have written a binary search like following. When I try to find 10, it's not showing me the result. What am I missing?? // BinarySearch.cpp : Defines the entry point for the console application. //

I have to implement a binary search tree using C++ for one of assignments. I've created the class, and attempted to implement the InsertItem, PrintTree, DeleteTree methods for the class, I think I did

I have a small doubt here... If I know that a search element in a list ,say containing 32 elements sorted in order, is appearing within first four positions, which is the best searching algorithm. Lin

I understand how binary search trees are implemented, but I am not sure what are the advantages of using it over the hash tables that most programming languages have built into their standard librarie

I wanted to optimize below code using openMP double val; double m_y = 0.0f; double m_u = 0.0f; double m_v = 0.0f; #define _MSE(m, t) \ val = refData[t] - calData[t]; \ m += val*val; #pragma omp paral

Ok, so I am currently trying to create a binary search tree, with each node containing a reference to some object, as well as a reference to its left child and a reference to its right child (3 variab

This is a C program with the recursive binary search algorithm, however when I run it, the debugger says there is an access segmentation fault in the binary search function. Why is this and how do I f

I am trying to implement an A* Search algorithm. For now I am just trying to find a good path through an environment littered with walls. The walls are randomly generated, and in some cases my path ge

I am trying to merge multiple sorted lists into one TreeSet.. And then I am thinking to apply Binary Search algorithm on that TreeSet to retrieve the element in O(log n) time complexity.. Below is my

I've been researching how to create binary search trees and i have run into a problem when trying to create my own. I have to use the following private structure to create the tree. Every example that

Here I have a query regarding the A Star Search Algorithm. I'm building what is known as the 8 piece puzzle. This is a game with 9 places (1 is empty) and you have to arrange the tiles in a correct or

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

Hi is there any clear algorithm that make a red black tree from a binary search tree? please help me thanks

The code below works but I want to optimize the code using yield or by changing algorithm. public IEnumerable<Book> GetAuthorWithBookName(string keyword) { var bookAndAuthorList = new List<Bo

I have two questions about binary search trees - one about the code I am writing and the other more about theory. First of all, the code that I wrote below works fine except for when I try to display

I have a question with regards to the Binary Search Tree Implemetation in C++. Here is the question below Implement a simple (non-templated) BST which stores integers. Provide the following operations

This may be a silly question, but does anyone know of a proof that binary search is asymptotically optimal? That is, if we are given a sorted list of elements where the only permitted operation on tho

I'm trying to implement a recursive binary search, after looking at the example on this textbook page. My algorithm seems to work fine in most cases, but on values higher than the highest value in the

I have been trying to implement a binary search on a sorted array of data with an application for cubic spline interpolation. I am unable to get it to function on all the range. For instance, search n

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'm reading up on Binary Search Trees and I have a question to answer similar to Ordered Binary Tree of Strings Are the trees I've drawn below correct for before and after balancing? The data being en

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 ?

A cry for help to all those good at suggesting fast algorithms, specifically search algorithms! I'm trying to optimise some MATLAB code which looks for 'coincidences' in a list of chronologically orde

I am implementing code to construct BST(binary search tree) from a given post-order traversal array following this algorithm. I do not get back the binary Search Tree back. I am getting something that

I have written the next algorithm (for Android/NDK) to apply levels to a bitmap. The problem is that is really very slow, on a fast device such as the SGSIII can take up to 4 seconds for a 8MP image.

The list is sorted. I have a List and I d like to do binary search on it. T has members like StartIndex, EndIndex etc. I can do binary search on the list with StartIndex, ie: I have implemented ICompa

Do you memorize algorithms such as binary search / quick sort / whatever. If so, do you have any tricks for doing so?

My Code below is not working, not giving me any output. It was working well when I asked users to enter set of numbers and find within. But when I tried to search within random numbers, it is not work

For starters this is homework, I just really need help with a binary search tree. The program is to display polymorphism, using person as an abstract base class, and other types of people which inheri

Introduction I'm building an HTML5 web application that creates a visual representation of a binary search tree from a given list of numbers. Currently, I have an algorithm which calculates the visual

In my program I need to search in a quite big string (~1 mb) for a relatively small substring (< 1 kb). The problem is the string contains simple wildcards in the sense of a?c which means I want

I recently finished implementing a Binary search tree for a project I was working on. It went well and I learned a lot. However, now I need to implement a regular Binary Tree... which for some reason

how do i represent binary search trees in python?

This is some code found on wikipedia regarding BST : # 'node' refers to the parent-node in this case def search_binary_tree(node, key): if node is None: return None # key not found if key < node.k

I am trying to implement a search algorithm in my simple datastructure. However, this is not a HOW DO I DO THIS?-question, but rather a how could i optimize the algorithm? I am trying to keep a in

I am trying to build a binary search tree, however, it is vital for the algorithm that I am implementing to do so with a vector to diminish cache misses. My original idea was to adapt something simila

I am looking for a built-in Ruby method that has the same functionality as index but uses a binary search algorithm, and thus requires a pre-sorted array. I know I could write my own implementation, b

A friend was recently interviewed for a position at a tech company and was given 4 programming tasks. One of the tasks was to implement a Binary Search Tree class using a Linked List implementation w

I use standard binary search to quickly return a single object in a sorted list (with respect to a sortable property). Now I need to modify the search so that ALL matching list entries are returned.

I'm currently implementing a Binary Search Tree and got stuck at merging it with another. So far I've got: head: returns node with smallest node tail: returns tree w/o smallest node insert(value): co

I need help writing a program that uses binary search to recursively compute a square root (rounded down to the nearest integer) of an input non-negative integer. This is what I have so far: import ja

I have a sorted list of binary vectors, let's call it L, and I have a binary vector q, how can I find the vectors in L that are closest to q using binary search?

This question already has an answer here: Implementing a binary insertion sort using binary search in Java 2 answers When implementing Insertion Sort, a binary search could be used to locate th

Possible Duplicate: What are the pitfalls in implementing binary search? I was perusing the wikipedia page for Binary Search and stumbled on a quote by Knuth below: Although the basic idea of bina

Does anyone know how to calculate the complexity of a nested binary search tree? I have implemented a nested binary search tree to a depth of 3 BSTs. EDIT: I apologize for the confusion, I had meant

This program is suppose to detect if an integer is found or not and how long it took to find. The first one is a linear search and the second is a binary search. The problems I'm having is this. The l

I want to make a search page like google that when i input 'ex' then with the ajax we recognition that the user intend to input 'example' or 'exam' or ... what is the algorithm for making a page like

I use inorder to show result of search name which store in binary search tree but when i run it example i have: Employee name abc and ab and i input name =abc it show 2 of them.Anyone can help m

How can I create/delete a node in a Binary Search Tree using Iterative Algorithm in C?