C++ Program to Implement Binary Search using Iteration

This is a C++ Program to implement Binary Search Algorithm.

Problem Description

We have to write a C++ Program which either finds the position of an element in an array or detects the presence of an element in an array using Binary Search Algorithm.

Expected Input and Output

Case 1. Average Case: When the element to be searched for is any random element from the array.

If the input array is {1, 2, 3, 4, 5, 6}
and the element to be searched for is 6,
then the output will be SEARCH SUCCESSFUL.

Average case time complexity: O(log n)

Case 2. Best case: When the element to be searched for is the middle element of the array.

If the input array is {-3, 31, 66}
and the element to be searched is 31,
then the output will be SEARCH SUCCESSFUL.

Best case time complexity: O(1)

Case 3. Worst Case: When the element searched for is absent and it is either smaller or greater than all the elements.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If the input array is {1, 1, 3, 6, 9}
and the element to be searched for is 10,
then the output will be SEARCH FAILED

Worst case time complexity: O(log n)

Problem Solution

We will be having an array of numbers, we just need to find out the position of an element in the array if it is present. It can be done using Linear Search but it takes up a lot of time, so we need a better searching algorithm that performs the same task but in less time in comparison to Linear Search. In worst case Linear Search takes O(n) time, but Binary Search takes O(log n) time.

Program/Source Code

Here is source code of the C++ Program to find the position of an element requested by the user using Binary Search Algorithm using iteration. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

```
/*
```

 * C++ program to accept N numbers sorted in ascending order

 * and to search for a given number using Binary Search.

```
 * Report success or failure.
```
```
 */
```
```
#include <iostream>
```
```
using namespace std;
```
```
class BS
```
```
{
```
```
public:
```
```
    /*
```
```
     * Binary Search function
```
```
     */
```

    void BinarySearch(int array[], int keynum, int num)

```
    {
```
```
        int low = 1;
```
```
        int high = num;
```
```
        int mid;
```
```
    do
```
```
    {
```
```
        mid = (low + high) / 2;
```
```
        if (keynum < array[mid])
```
```
        {
```
```
            high = mid - 1;
```
```
        }
```
```
   	else if (keynum > array[mid])
```
```
        {
```
```
            low = mid + 1;
```
```
        }
```
```
	}
```

	while (keynum != array[mid] && low <= high);

```
        if (keynum == array[mid])
```
```
        {
```

            cout<<"SEARCH SUCCESSFUL \n";

```
        }
```
```
        else
```
```
        {
```
```
            cout<<"SEARCH FAILED \n";
```
```
        }
```
```
    }
```
```
};
```
```
int main()
```
```
{
```
```
    int array[10];
```
```
    int i, j, num, temp, keynum;
```
```
    int low, mid, high;
```
```
    cout<<"Enter the value of num \n";
```
```
    cin>>num;
```

    cout<<"Enter the elements one by one \n";

```
    for (i = 0; i < num; i++)
```
```
    {
```
```
        cin>>array[i];
```
```
    }
```
```
    /*
```
```
     * Bubble sort
```
```
     */
```
```
    for (i = 0; i < num; i++)
```
```
    {
```

        for (j = 0; j < (num - i - 1); j++)

```
        {
```

            if (array[j] > array[j + 1])

```
            {
```
```
                temp = array[j];
```

                array[j] = array[j + 1];

```
                array[j + 1] = temp;
```
```
            }
```
```
        }
```
```
    }
```

    cout<<"Enter the element to be searched \n";

```
    cin>>keynum;
```
```
    // Binary searching begins
```
```
    BS b1;
```

    b1.BinarySearch(array, keynum, num);

```
    return 0;
```
```
}
```

Program Explanation

1. Here in this program we have first requested the array of numbers and the value to be searched from the user.
2. Since binary search is applied upon a sorted array we have created a separate bubble sort function to sort the array before searching.
3. After sorting the array we have passed the array to the function called BinarySearch(array, keynum, num) having array, key and the size of array as its parameters.
4. In BinarySearch(array, keynum, num) we first find the middle index of the array, and then compare the key with the middle element of array i.e. array[middle].
5. If key is less than the middle element of array we divide the array in to two halves i.e. low to mid-1 and (mid+1) to high, where mid is the middle index, low is the starting and high is the ending index of the array. After dividing the array we start searching in the left half of the array i.e. low to mid-1.
6. If the key is greater than the middle element then we search in the right half of the array i.e mid+1 to high.
7. In each iteration we divide the array until it has only 1 element left.
8. If we are able to find the element we print “SEARCH SUCCESSFUL” otherwise we print “SEARCH FAILED”.

Runtime Test Cases

1. Enter the value of num
   6
   Enter the elements one by one
   1 2 3 4 5 6
   Enter the element to be searched
   6
   SEARCH SUCCESSFUL
 
2. Enter the value of num
   3
   Enter the elements one by one
   -3 31 66
   Enter the element to be searched
   31
   SEARCH SUCCESSFUL
 
3. Enter the value of num
   5
   Enter the elements one by one
   1 1 3 6 9
   Enter the element to be searched 
   10
   SEARCH FAILED

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Implement Linear Search using Recursion

» Next - C++ Program to Implement Sieve of Eratosthenes

Related Posts:

Recommended Articles: