Binary Search Algorithm

BinarySearch.cpp

// Binary Search Algorithm

/*
 1. ask user the size of array
 2. declare the array
 3. ask user the limit and range of random numbers
 4. initialize the array with random numbers
 5. print the array
 6. sort the array in ascending order
 7. print sorted array
 8. ask user to search for a number
 9. apply binary search algorithm
 10. print the result
 */

#include<iostream>
#include<cstdlib>
using namespace std;

int main()
{
    cout<<"»»————- вínαrч sєαrch αlgσríthm ————-««"<<endl;
    cout<<endl;
    
    cout<<"This program will perform the following tasks: "<<endl;
    cout<<"1. ask user the size of array"<<endl;
    cout<<"2. declare the array"<<endl;
    cout<<"3. ask user the limit and range of random numbers"<<endl;
    cout<<"4. initialize the array with random numbers"<<endl;
    cout<<"5. print the array"<<endl;
    cout<<"6. sort the array in ascending order"<<endl;
    cout<<"7. print sorted array"<<endl;
    cout<<"8. ask user to search for a number"<<endl;
    cout<<"9. apply binary search algorithm"<<endl;
    cout<<"10. print the result"<<endl;
    
    cout<<endl<<endl;
    
    //....................................................................
    
    // 1. ask user the size of array
    
    int size;
    cout<<"How many numbers you want to enter: ";
    cin>>size;
    
    cout<<endl<<endl;
    
    // 2. declare the array
    
    int array[size];
    
    // 3. ask user the limit and range of random numbers
    
    cout<<"For entering random numbers ..."<<endl;
    
    int a, b, c;
    
    cout<<"Enter the starting limit of numbers: ";
    cin>>b;
    
    cout<<"Enter the ending limit of numbers: ";
    cin>>c;
    
    a = c - b;
    
    cout<<endl<<endl;
    
    // 4. initialize the array with random numbers
    
    for(int i=0; i<size; i++)
    {
        array[i] = (rand() % a + b);
    }
    
    // 5. print the array
    
    cout<<"Following numbers are entered randomly: "<<endl;
    
    for(int i=0; i<size; i++)
    {
        cout<<array[i]<<"   ";
    }
    
    cout<<endl<<endl;
    
    //....................................................................
    
    //  6. sort the array in ascending order
    int swap = 0;
    
    for(int i=0; i<size; i++)
    {
        for(int j=0; j<((size - 1) - i); j++)
        {
            if(array[j] > array[j + 1])
            {
                swap = array[j + 1];
                array[j + 1] = array[j];
                array[j] = swap;
            }
        }
    }
    
    // 7. print sorted array
    
    cout<<"The numbers in ascending order are: "<<endl;
    
    for(int i=0; i<size; i++)
    {
        cout<<array[i]<<"   ";
    }
    
    cout<<endl<<endl;
    
    //....................................................................
    
    //  8. ask user to search for a number
    
    int find;
    cout<<"Enter a number to find: ";
    cin>>find;
    
    cout<<endl;
    
    // 9. apply binary search algorithm
    // 10. print the result
    
    int first = 0;
    int last = size - 1;
    int middle = (first + last) / 2;
    
    while(first <= last)
    {
        if(array[middle] < find)
        {
            first = middle + 1;
        }
        else if(array[middle] == find)
        {
            cout<<"The number "<<find<<" is found at position: "<<(middle+1);
            cout<<endl;
            break;
        }
        else // if(array[middle] > find
        {
            last = middle - 1;
        }
        
        middle = (first + last) / 2;
    }
    
    if(first > last)
    {
        cout<<"The number "<<find<<" is NOT found"<<endl;
    }
    
    cout<<endl<<endl;
    
    return 0;
    
    // The End
    
    
}