First off, what is a binary search? A binary search, also known as a half-interval search, is an algorithm that finds a target number in a sorted sequence of numbers by comparing the target number to the middle number in the sequence. If the target number is smaller than the middle number, the entire top half of the sequence is ignored.
Let’s break this down with an example. Let’s say we’re looking for the number 51 in this range of numbers
There are 16 numbers in this sequence, and in computer programming, we begin counting sequences of numbers at 0, which makes the middle number in this sequence
121. In this case, 51 is less than 121, so every number greater than 121, and 121 itself is ignored, making the sequence of numbers look like this:
Now that we have 8 numbers in the sequence, the middle number is
47. Since 51 is a larger number, we can ignore all the numbers 47 on down, leaving us with
15 89 100. Once again we take the middle number,
89. 51 is smaller, so we ignore 89 and 100, leaving us with just 15. If our target number is 15, we have officially found our target.
So how do we write this in C?
First things first, we need an array that holds all 16 numbers:
Next we need to define our own search function:
1 2 3 4 5
This function, called
search takes in 3 arguments, the target number that you’re looking for,
value, the array that you’re searching through,
values, and the length of the array,
n. This method also returns false (or zero) in the case of success.
Now that we have the function set up, some pseudo-code to get us thinking in the right way:
- Set up a base case (if there is only 1 item in the array) so that the recursive loop will quit appropriately
- Create a variable to store the index of the middle number in the array
- Instantiate a new array from the correct half of the original array to search through
- Compare the target number to the middle number
- If the target number is greater than the middle number, ignore everything from the middle number down and store the larger numbers in a new array and vice versa
- Call search function to find the middle again….
Set up a base case
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
In this base case, the first if statement is checking to see if the size of the array
n, is less than one, meaning is there only one item in this array? If that statement evaluates to true, the nested if/else statement will kick in. The nested if statement is checking to see if the target number
value is the number in the array. If it is, the function will return false, if it isn’t it will return true.
Create a variable to store the index of the middle number in the array
The middle number in the array is going to be
n is 16, the middle number would be 8. If
n is 15, the middle number would be 7.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
On line 15, we set up a variable
middle to store the middle value.
Instantiate a new array from the correct half of the original array to search through
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
On lines 16 we create a new constant, which stores the number 65536. This massive number will be useful to gaurantee that the search function can handle incredibly large arrays. On line 17 we create a new array called
half, declare that it will store up to 65536 integers.
Compare the target number to the middle number
We’re going to need to set up more flow control based on the results of comparing
value to the middle number in the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Now we have our logic set up for either situation, if
value (the number we’re searching for) is either less than or greater than or equal to
values[middle], which is the number at the middle index of the
If the target number is greater than the middle number, ignore everything from the middle number down and store the larger numbers in a new array and vice versa
Once we’re inside our if statements, we need to be able to select just half of the original array, by storing it in the new array we instatiated previously.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
In the case that
value is greater than
values[middle], we want to take the top half of the
values array. We first create a
new_size variable which stores the size of the top half of the array (n - middle -1). Then we iterate over the top half of the
values array place the value of each index in the
half array. This for-loop needs to incrementors,
i which will iterate through
m which stores the index of the middle item in the array and iterates through
values. Once we have our new array, we need to call our search function again. This is recursive implementation of a binary search, which means we’re calling a function inside the definition of that function. Our function with return out when it hits the base case, aka when there is only one index left in the array.
value is less than
values[middle]? We need to take the bottom half of the
values array and place those values in an empty
half array. Again, we have to call our search function.
An important part here is how we call the search function recursively on lines 29 and 37,
return search(value, new_array, new_size);. We need to explicitly return the return value of those recursive calls so that they can move up the tree and the original search function can return the result.