Binary Search Algorithm, written in C [with video example step-to-step]

In computer science, a binary search is an algorithm for locating the position of an item in a sorted array.[1][2] Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element is equal to the input, less than the input or greater. When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array’s elements. If the input is not located within the array the algorithm will usually output a unique value indicating this. This method halves the number of items to check each time, so it finds it or determines it’s not present in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.
It is useful to find where an item is in a sorted array. For example, if you had an array for contact information, with people’s names, addresses, and telephone numbers sorted by name, you could use binary search to find out a few useful facts: whether the person’s information is in the array, what the person’s address is, and what the person’s telephone number is.

Binary search will take far fewer comparisons than a linear search, but there are some downsides. Binary search can be slower than using a hash table. If items are changed, the array will have to be re-sorted so that binary search will work properly, which can take so much time that the savings from using binary search aren’t worth it. If you can tell ahead of time that a few items are disproportionately likely to be sought, putting those items first and using a linear search could be much faster.

The algorithm

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… — Professor Donald Knuth

When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks (Kruse, 1999). Furthermore, Bentley’s own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.

Numerical difficulties

In a practical implementation, the variables used to represent the indices will be of finite size, hence only capable of representing a finite range of values. For example, 16-bit unsigned integers can only hold values from 0 to 65535. If the binary search algorithm is to operate on large arrays, this has two implications:

  • The values first − 1 and last + 1 must both be representable within the finite bounds of the chosen integer type . Therefore, continuing the 16-bit example, the largest value that last may take is +65534, not +65535. A problem exists even for the “inclusive” form of the method, as if x > A(65535).Key, then on the final iteration the algorithm will attempt to store 65536 into L and fail. Equivalent issues apply to the lower limit, where first − 1 could become negative as when the first element of the array is at index zero.
  • If the midpoint of the span is calculated as p := (L + R)/2, then the value (L + R) will exceed the number range if last is greater than (in our example) 65535/2 and the search wanders toward the upper end of the search space. This can be avoided by performing the calculation as p := (R - L)/2 + L. For example, this bug existed in Java SDK at Arrays.binarySearch() from 1.2 to 5.0 and fixed in 6.0.

Syntax difficulties

Another difficulty is presented by the absence in most computer languages of a three-way result from a comparison, which forces a comparison to be performed twice. The form is somewhat as follows:

<pre>if a &lt; b then action1
 else if a &gt; b then action2
  else action3;</pre>

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) by using an order such as

<pre>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.

Source code written in C


// © Codeido - www.codeido.com - Developed by Paolo Musolino

/* Ricerca binaria in un array ordinato */
#include <stdio.h>

int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

int ricerca_Binaria(int a[], int n, int chiave)
{
	int inf=0, sup=n-1, medio=0;
	
	while (a[medio]!=chiave)
	{
		medio=(inf+sup)/2;
		if (chiave>a[medio]) 
		{
			inf=medio+1; 
		}
		else if(chiave<a[medio])
		{
			sup=medio;
		}
		else if (chiave==a[medio])
		{
			return medio; //elemento trovato
		}
	    else {
			return -1;
		}

		
		
	}

}



int main ()
{
	int a[16]={1, 4, 5, 8, 10, 11, 12, 13, 14, 16, 18, 20, 22, 44, 88, 111};
	int ris_ricerca;
	ris_ricerca = ricerca_Binaria(a, 16, 111);
	printf("\n");
	
	if (ris_ricerca==-1) {
		printf("L'elemento cercato non è presente all'interno dell'array\n");
	}
	
	if (ris_ricerca>=0) {
		printf("L'elemento cercato si trova nella posizione %d ", ris_ricerca);
	}
	
	return 0;
}

15 thoughts on “Binary Search Algorithm, written in C [with video example step-to-step]

  1. Nice! I am quite interested in your site. If I were to use this website, I could earn you 200-1000 USD daily. I am willing to work on monetizing your site, on the condition that you share 50% of revenues with me. If you are interested, please send me an email. 😉

  2. This is my first time i visit here. I found so many interesting stuff in your website especially its discussion. From the tons of opinions on your articles, I guess I am not the only one having all the enjoyment here! keep up the excellent work.

  3. I love it when see people giving lessons using modern ways!
    Reading a tutorial for this algorithm would take me much more time!
    If I have to compare both the difference is like between the binary and linear search!

  4. This site appears to recieve a great deal of visitors. How do you advertise it? It offers a nice unique twist on things. I guess having something real or substantial to give info on is the most important factor.

  5. Magnificent goods from you, man. I have understand your stuff previous to and you are just extremely magnificent. I really like what you have acquired here, certainly like what you’re saying and the way in which you say it. You make it entertaining and you still take care of to keep it sensible. I can not wait to read much more from you. This is actually a tremendous web site.

Leave a Reply to porno film Cancel reply

Your email address will not be published. Required fields are marked *