beginnersbook.com

  • Home
  • All Tutorials
    • Learn Servlet
    • Learn JSP
    • Learn JSTL
    • Learn C
    • Learn C++
    • Learn MongoDB
    • Learn XML
    • Learn Python
    • Learn Perl
    • Learn Kotlin
  • Core Java
  • OOPs
  • Collections
  • Java I/O
  • JSON
  • DBMS

C++ Program for Binary Search

By Chaitanya Singh | Filed Under: C++ Programs

This C++ program searches the entered number in the list of numbers using binary search algorithm and returns the location of the input number if it is found in the list.

Example: Binary Search Program in C++

Binary search algorithm searches the target value within a sorted array.

  • To perform a binary search array must be sorted, it should either be in ascending or descending order.
  • Step 1: First divide the list of elements in half.
  • Step 2: In the second step we compare the target value with the middle element of the array. If it matches the middle element then search ends here and doesn’t proceed further.
  • Step 3: Else if the element less than the middle element then we begin the search in lower half of the array.
  • Step 4: Else if the element is greater than the middle element then we begin the search in greater half of the array.
  • Step 5: We will repeat the steps 3 ,4 and 5 until our target element is found.
#include <iostream>
using namespace std;

int binarySearch(int[], int, int, int);

int main()
{
   int num[10] = {10, 22, 37, 55, 92, 118};
   int search_num, loc=-1;

   cout<<"Enter the number that you want to search: ";
   cin>>search_num;

   loc = binarySearch(num, 0, 6, search_num);

   if(loc != -1)
   {
      cout<<search_num<<" found in the array at the location: "<<loc;
   }
   else
   {
      cout<<"Element not found";
   }
   return 0;
}

int binarySearch(int a[], int first, int last, int search_num)
{
   int middle;
   if(last >= first)
   {
      middle = (first + last)/2;
      //Checking if the element is present at middle loc
      if(a[middle] == search_num)
      {
         return middle+1;
      }

      //Checking if the search element is present in greater half
      else if(a[middle] < search_num)
      {
         return binarySearch(a,middle+1,last,search_num);
      }

      //Checking if the search element is present in lower half
      else
      {
         return binarySearch(a,first,middle-1,search_num);
      }

   }
   return -1;
}

Output:

Enter the number that you want to search: 55
55 found in the array at the location: 4

C++ Program for Binary Search

Enjoyed this post? Try these related posts

  1. C++ Program to Find Second Smallest Element in an Array
  2. C++ Program to find number of Digits and White Spaces in a String
  3. C++ Program to Display the Number Entered by User
  4. C++ Program to Add two Matrices
  5. C++ Program to Find largest element in an array
  6. C++ Program to Convert Uppercase to Lowercase

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Programs

  • C Programs
  • Java Programs

Recently Added..

  • JSON Tutorial
  • Java Regular Expressions Tutorial
  • Java Enum Tutorial
  • Java Annotations Tutorial

Copyright © 2012 – 2021 BeginnersBook . Privacy Policy . Sitemap