Binary Search in C++

        To implement binary search the array must be sorted, if you don't sort it may give the wrong output. Take the array size and array elements. Sort the array in ascending order. Take the element the user wants to search.

        The trick in binary search is you find the middle element of the array by adding the first and last element and dividing the sum by 2. Then compare the middle element if the required element. If the middle element is a greater search on the right side of the array else search on the left side of the array.

        Time complexity is O(log n) of binary search algorithm.

How do I calculate the middle element?

middle = first + last / 2

where, 

first = 0

last = array size - 1

Code

#include <bits/stdc++.h>

using namespace std;

int main() 

{   

    int n;                          // array size

    cin>>n;

    

    int a[n];                       // array

    for(int i=0;i<n;i++){

        cin>>a[i];

    }

    

    sort(a,a+n);                    // sort the array know more about sort in c++ here

    

    int s;                                      // to store searching element

    cout<<"Enter the element to search: ";

    cin>>s;

    

    int first=0;                    // first index

    int last=n-1;                  // last index

    int mid=(first+last)/2;       // finding the middle element

    int flag=0;                  // to check the element is found or not primarily set to 0(not found)

    

    

    if(a[mid]<s){

        for(int i=mid;i<n;i++){         // loop to check the elements from mid to the end

            if(a[i]==s){

                flag=1;                     // element found update flag and break the loop

                break;

            }

        }

    }

    else{

        for(int i=0;i<=mid;i++){              // loop to check the elements from zero to mid

            if(a[i]==s){

                flag=1;                     // element found update flag and break the loop

                break;

            }

        }

    }

    

    if(flag==0){                            // if flag is zero print element not found

        cout<<"Element not found";

    }

    else{                                   // flag is one print element is found

        cout<<"Element found";

    }

    

    return 0;

}

Output

5

500 3 45 999 78

Enter the element to search: 3

Element found

Program may also be asked as: 

1. Execute binary search algorithm
2. What is binary search complexity execute code
3. Execute binary search in c++ without recursion
4. Execute binary search in c++ using recursion
5. Execute binary search in c++ using function
6. Execute binary search in cpp algorithm
7. Write binary search code in c++
8. Write algorithm for binary search in c++
9. Write binary search program in data structure
10. Execute recursive binary search in c++
11. Write code for binary search in c++
12. Write a program to implement binary search in c++