Binary search in C\C++ (Algorithm, Pseudocode and output)
The goals of binary search are to :
- be able to discard half of the array at every iteration
- to Minimize the number of elements we have to go through and leave us with one final value.
- Working :
The working of the Binary Search can be better explained with the help of an example. So let's take for example the following array of integers :
int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };
Let’s say we are trying to find the index value of the number 7 in this array. There are 17 items in total and the index values go from 0 to 16.
Here we can see that the index value of 7 is 4 since it’s the fifth element in the array.
But what would be the best way for the computer to find the index value of the number we are looking for?
First, we store the
min
and max
values, such as 0
and 16
.int min = 0; int max = 16;
Now we have to come up with a guess. The smartest thing to do would be to guess an index value in the middle of the array.
With the index value 0 to 16 in this array, the middle index value of this array would be 8. That holds the number 14.
// This will round down if the quotient is not an integer
int guess = (min + max) / 2;
Our guess is now equal to 8, which is 14 in the array since
array[8]
is equal to 14
.
If the number we were looking for was 14, we would be done!
Since that is not the case, we will now discard half of the array. These are all the numbers after 14, or index value 8 since we know that 14 is greater than 7, and our guess is too high.
After the first iteration, our search is now within:
1, 3, 4, 6, 7, 8, 10, 13
We don’t have to guess in the last half of the original array, because we know that all those values are too big. That’s why it’s important that we apply binary search to an ordered list.
Since our original guess of 14 was greater than 7, we now decrease it by 1 and store that into
max
:max = guess - 1; // max is now equal to 7, which is 13 in the array
Now the search looks like this:
1, 3, 4, 6, 7, 8, 10, 13
min = 0 max = 7 guess = 3
Because our guess was too low, we discard the bottom half of the array by increasing the
min
, conversely to what we previously did to max
:min = guess + 1; // min is now 4
By the next iteration, we are left with:
7, 8, 10, 13 min = 4 max = 7 guess = 5
Since index value 5 returns 8, we are now one over our target. We repeat the process again, and we are left with:
7 min = 4 max = 4 guess = 4
And we are left with only one value, 4, as the index of the target number we were looking for, which was 7.
The purpose of binary search is to get rid of half of the array at every iteration. So we only work on those values on which it makes sense to keep guessing.
The pseudo-code for this algorithm would look something like this:
- Let
min = 0
, and letmax = n
wheren
is the highest possible index value - Find the average of
min
andmax
, round down so it’s an integer. This is ourguess
- If we guessed the number, stop, we got it!
- If
guess
is too low, setmin
equal to one more thanguess
- If
guess
is too high, setmax
equal to one less thanguess
- Go back to step two.
C++ Code for Binary Search
Following C++ program first, ask the user to enter "how many element he/she want to store in array", then ask to enter the array elements. After storing the element in the array, program ask to the user to enter the element which he/she want to search in the array whether that number is present or not.
The searching technique used here is binary search which is a fast technique :
#include <iostream>
using namespace std;
int main()
{
int count, i, arr[30], num, first, last, middle;
cout<<"how many elements would you like to enter?:";
cin>>count;
for (i=0; i<count; i++)
{
cout<<"Enter number "<<(i+1)<<": ";
cin>>arr[i];
}
cout<<"Enter the number that you want to search:";
cin>>num;
first = 0;
last = count-1;
middle = (first+last)/2;
while (first <= last)
{
if(arr[middle] < num)
{
first = middle + 1;
}
else if(arr[middle] == num)
{
cout<<num<<" found in the array at the location "<<middle+1<<"\n";
break;
}
else {
last = middle - 1;
}
middle = (first + last)/2;
}
if(first > last)
{
cout<<num<<" not found in the array";
}
return 0;
}
Output
how many elements would you like to enter?:5 Enter number 1: 23 Enter number 2: 55 Enter number 3: 64 Enter number 4: 22 Enter number 5: 11 Enter the number that you want to search:32 32 not found in the array.
C code for Binary Search
#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter value to find\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d isn't present in the list.\n", search);
return 0;
}
Output
Enter number of elements 3 Enter 3 integers 21 32 66 Enter value to find 32 32 found at location 2.
No comments
If you have any doubts, please let us Know.