Exercise: Binary Search

When you need to check if the given number in an arbitrary array, linear search is the best you can do: you inevitably need to check all elements of the array and compare each of them with the number you're looking for.

But if you know that the array is sorted, so that its elements only increase–like a phone book or an alphabetical index–then you don't need to go through all of the elements to check if the number you need is there or not.

Let's look at the following sorted array of 7 numbers:

1 3 5 7 9 11 13

Let's try to find out if 11 is in this array. We know that its elements only increase, so if we look at the element in the middle, we can get a quick idea if the number we look for is on the left or on the right of the middle element. The number in the middle is 7, 11 is greater than 7, so we go right. That means that if we originally looked at elements between 0th and 6th (including both ends), and the middle element is the 3rd, then now we are going to look at elements between 4th and 6th:

index:  0  1  2  3  4  5  6
element:  1  3  5  7  9 11 13

1st step [        mid        ]
2nd step             [  mid  ]

On the second step we see that the middle element is 11, which is what we are looking for, so we finished our search in 2 steps.

Let's look at one more example, this time we'll try to look for 4, which is not in the array. How would that work?

index:  0  1  2  3  4  5  6
element:  1  3  5  7  9 11 13

1st step [        mid        ]
2nd step [  mid  ]

On the first step we compare 4 to 7 and figure out that it's on the left from the middle element. The middle element is the 3rd, so on the second step the range we care about is from 0th to 2nd element. The middle element (element #1, counting from zero) is 3, and 4 is greater than 3, which means we need to go right, and our range is now from 2nd to 2nd:

index:  0  1  2  3  4  5  6
element:  1  3  5  7  9 11 13

1st step [        mid        ]
2nd step [  mid  ]
3rd step      [mid]

On the third step, the middle element is 5, 4 is less than 5 so we should go left, but we don't have any remaining elements, which makes us believe that 4 cannot be found in this array. We used 3 comparisons to come to this conclusion.

We'll talk about the number of comparisons that the binary search requires very soon, but for now, let's write the code!

The input will look the same as it did for the linear search:

5            - number of elements
1 3 5 77 199 - elements, in an ascending order, followed by numbers to search:
1
2
3
77
100
199
200

For this input, the correct answer would be

0
-1
1
3
-1
4
-1

To implement binary search, declare two variables, l and r, pointing to the left end and the right end of the range you look at. Initially, l = 0 and r = N - 1, where N is the number of elements in the array.

Calculate the middle element. Remember that when you divide an int value by an int value, you get integer division, for example, 5 / 2 is 2. Look at the element in the middle: is it the number you're looking for? If not, decrease the range either by setting the left boundary to mid + 1, or the right boundary to mid - 1. Continue while your range is not empty.

Make sure your range decreases at every step, otherwise your code might hang forever!

Ready to try?

#include <stdio.h>

int binary_search(int element, int *arr, int size) {
	/* your code here */

	return -1;
}

int main() {
	int arr[10000];
	int size;

	/* your code here: read size */
	/* your code here: read array elements */

	/* your code here: read the remaining numbers
     and call binary_search for each one, and print the result
   */

	return 0;
}

On the next page we'll talk a little bit about the number of comparison these two searches – linear search and binary search – perform, and the code complexity!