Binary search in C\C++ (Algorithm, Pseudocode and output)

Hy guys welcome to Another tutorial on searching Algorithms. In this tutorial, you will learn about Binary Search and its programs both in C and c++

Binary search is one of those algorithms that you’ll come across in every (good) introductory computer science class. It’s an efficient algorithm for finding an item in an ordered list. For the sake of this example, we’ll just assume this is an array.

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:

1. Let min = 0 , and let max = n where n is the highest possible index value
2. Find the average of min and max , round down so it’s an integer. This is our guess
3. If we guessed the number, stop, we got it!
4. If guessis too low, set min equal to one more than guess
5. If guessis too high, set max equal to one less than guess
6. 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.

So this is it guys if you want us to write more on this topic or have any particular query regarding this post you can always comment or feel free to mail us at our official mail also follow us on Instagram and Facebook to receive Latest Updates first.

PEACE!!!