C++ Program for Binary Search in a Sorted Array.

on

The following program will perform Binary Search in a sorted array to find an element.


Binary Search Image Representation.

C++ Program for Binary Search in a Sorted Array:

We will go through some questions first to get a better understanding of binary search before moving towards the program.

What is Binary Search:

Binary Search is a type of effective searching technique to find that an element is present in an array or not. Unlike Linear Search (which is checking all the elements of the array to find the required element), Binary search can only be performed on Sorted Arrays. It is more efficient than linear searching as binary search lower the search to half of the elements of the array after every comparison made.

How this Works:

Steps:

The array must be sorted in ascending or descending order. Here I am considering an array that is sorted in ascending order.
  1. Find the middle element of the array => (lowerbound + upperbound)/2
  2. Compare the middle element with the required number. If the middle element matches the required element then the search ends here.
  3. Else if the required element is less than the middle element, we search the left half of the array. (This is the step where half of the searches are reduced).
  4. Else if the required element is greater than the middle element, we search the right half of the array.
  5. Continue steps 2, 3, 4 unless an element is found or a terminating condition is matched.
The loop will terminate if the lower bound of the array becomes greater than the upper bound of the array.
Now, let's move to the source code of the program.

Source Code:

#include <iostream>

using namespace std;

int main()
{
    int sizeOfArray = 20;
    int arr[sizeOfArray];
    for (int i = 0; i < sizeOfArray; i++)
    {
        arr[i] = i+1;
    }
    
    
    
    int found = false;
    int lb = 0;  // array index start from 0.
    int ub = sizeOfArray - 1; // ending index.
    int middle = 0;
    
    cout << "Enter the number which you want to search: ";
    int item;
    cin >> item;
    
    while (lb <= ub)
    {
        middle = (lb+ub)/2;
        if (arr[middle] == item)
        {
            cout << item << " is present in the array at index " << middle << "." << endl; 
            found = true;
            break;
        }
        else if (item < arr[middle])
        {
            ub = middle-1;
        }
        else
        {
            lb = middle+1;
        }
    }
    if (found == false)
    {
        cout << item << " is not found in the array" << endl;
    }

    // printing original array:
    cout << "Original Array:" << endl;
    for (int i = 0; i < sizeOfArray; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

Output:

Enter the number which you want to search: 5
5 is present in the array at index 4.
Original Array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Alternate Output:

Enter the number which you want to search: 25
25 is not found in the array
Original Array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Key Points:

  • Binary Search can only be performed on sorted arrays.
  • Binary Search is more efficient than linear search in case of sorted arrays.
  • Binary Search cannot be performed on linked lists.

If you have any queries about this program or about anything, do ask in a comment. I will try to answer as many questions as I can.

Comments

Post a Comment