Binary Search in C++

We will discuss the binary search in the C++ programming language. Binary search is a mechanism used to find the given elements from the sorted array by continuously halving the array and then searching specified elements from a half array. And the process goes on till the match is found. It works only the sorted data structures. The time complexity of the binary search algorithm is O (log n).

Note: To perform a binary search technique in C++, a programmer or user should ensure the given array must be sorted either be in ascending or descending order.

Algorithm of the binary search in C++

Following is the algorithm to perform the binary search in C++

  beg = 0;  end = size – 1;  while ( beg <= end)  {  // calculate mid value  mid = (beg + end) / 2;  /* if the specified element is found at mid index, terminate the process and return the index. */  // Check middle element is equal to the defined element.  If (aarr[mid] == num)  {  return mid + 1;  }  else if (arr[mid] > num)  {  End = mid – 1;  }  Else if (arr [mid] < num)  {  Beg = mid + 1;  }  }  // If the element does not exist in the array, return -1.  Return -1;   

Steps to perform the binary search in C++

Step 1: Declare the variables and input all elements of an array in sorted order (ascending or descending).

Step 2: Divide the lists of array elements into halves.

Step 3: Now compare the target elements with the middle element of the array. And if the value of the target element is matched with the middle element, return the middle element’s position and end the search process.

Step 4: If the target element is less than the middle element, we search the elements into the lower half of an array.

Step 5: If the target element is larger than the middle element, we need to search the element into the greater half of the array.

Step 6: We will continuously repeat steps 4, 5, and 6 till the specified element is not found in the sorted array.

Example 1: Program to find the specified number from the sorted array using the binary search

Let’s write a program to find the specified number from a sorted array using the binary search in the C++ programming language.

  #include <iostream>  #include <conio.h>  using namespace std;  int main ()  {  // declaration of the variables and array  int arr[100], st, mid, end, i, num, tgt;    cout << ” Define the size of the array: ” << endl;  cin >> num; // get size    // enter only sorted array          cout << ” Enter the values in sorted array either ascending or descending order: ” << endl;  // use for loop to iterate values  for (i = 0; i < num; i++)  {  cout << ” arr [” << i << “] = “;  cin >> arr[i];  }    // initialize the starting and ending variable’s values  st = 0;  end = num – 1; // size of array (num) – 1    // define the item or value to be search  cout << ” Define a value to be searched from sorted array: ” << endl;  cin >> tgt;    // use while loop to check ‘st’, should be less than equal to ‘end’.  while ( st <= end)  {  // get middle value by splitting into half  mid = ( st + end ) / 2;  /* if we get the target value at mid index, print the position and exit from the program. */  if (arr[mid] == tgt)  {  cout << ” Element is found at index ” << (mid + 1);  exit (0); // use for exit program the program  }  // check the value of target element is greater than the mid element’ value  else if ( tgt > arr[mid])  {  st = mid + 1; // set the new value for st variable  }    // check the value of target element is less than the mid element’ value  else if ( tgt < arr[mid])  {  end = mid – 1; // set the new value for end variable  }  }  cout << ” Number is not found. ” << endl;  return 0;  }   

Output

Define the size of the array:   10  Enter the values in sorted array either ascending or descending order:  Arr [0]  = 12  Arr [1]  = 24  Arr [2]  = 36  Arr [3]  = 48  Arr [4]  = 50  Arr [5]  = 54  Arr [6]  = 58  Arr [7]  = 60  Arr [8]  = 72  Arr [9]  = 84  Define a value to be searched from sorted array:  50  Element is found at index 5

Example 2: Program to perform the binary search using the user-defined function

  /* program to find the specified element from the sorted array using the binary search in C++. */  #include <iostream>  using namespace std;  /* create user-defined function and pass different parameters:  arr[] – it represents the sorted array;  num variable represents the size of an array;  tgt variable represents the target or specified variable to be searched in the sorted array. */  int bin_search (int arr[], int num, int tgt)  {  int beg = 0, end = num – 1;  // use loop to check all sorted elements  while (beg <= end)  {  /* get the mid value of sorted array and then compares with target element. */  int mid = (beg + end) /2;  if (tgt == arr[mid])  {  return mid; // when mid is equal to tgt value  }  // check tgt is less than mid value, discard left element  else if (tgt < arr[mid])  {  end = mid – 1;  }  // if the target is greater than the mid value, discard all elements  else {  beg = mid + 1;  }  }  // return -1 when target is not exists in the array  return -1;  }  int main ()  {  // declaration of the arrays  int arr[] = { 5, 10, 15, 20, 25, 30, 37, 40};  int tgt = 25; // specified the target element  int num = sizeof (arr) / sizeof (arr[0]);  // declare pos variable to get the position of the specified element  int pos = bin_search (arr, num, tgt);  if (pos != 1)  {  cout << ” Element is found at position ” << (pos + 1)<< endl;  }  else  {  cout << ” Element is not found in the array” << endl;  }  return 0;  }  

Output

Element is found at position 5

In the above program, we declared an array arr[] = {5, 10, 15, 20, 25, 30, 35, 40); and then we specified number ’25’ to which search from the sorted array using the binary search method. Therefore, we create a user-defined function bin_search() that searches the given number and returns the statement “Element is found at position 5″. If the number is not defined in the array, the bin_search() function shows ” Element is not found in the array.”

Example 3: Program to find the specified element using the recursion function

Let’s create an example to check whether the specified element is found in the sorted array using the binary search inside the recursion function.

  /* find the specified number using the binary search technique inside the recursion method. */  #include <iostream>  using namespace std;  // define a function  int binary_search (int [], int, int, int);  int main ()  {  // declaration of the variables  int i, arr[100], tgt, num, ind, st, end;  cout << ” Define the size of an array: “;  cin >> num;  cout << ” Enter ” << num << ” elements in ascending order: ” << endl;  // use for loop to ieterate the number  for ( i = 0; i < num; i++)  {  cout << ” arr [” << i << “] = “;  cin >> arr[i];  }  // define the element to be search  cout << ” n Enter an element to be searched in ascending array: “;  cin >> tgt;  // ind define the index number  ind = binary_search (arr, 0, num – 1, tgt);  // check for existemce of the specified element  if (ind == 0)  cout << tgt << ” is not available in the array-list”;  else  cout << tgt << ” is available at position ” << ind << endl;  return 0;  }  // function defnition  int binary_search (int arr[], int st, int end, int tgt)  {  int mid;  // check st is greater than end  if (st > end)  {  return 0;  }  mid = (st + end) / 2; // get middle value of the sorted array    // check middle value is equal to target number  if (arr[mid] == tgt)  {  return (mid + 1);  }  // check mid is greater than target number  else if (arr[mid] > tgt)  {  binary_search (arr, st, mid – 1, tgt);  }  // check mid is less than target number  else if (arr [mid] < tgt)  {  binary_search (arr, mid + 1, end, tgt);  }  }  

Output

Define the size of an array: 10  Arr [0] = 2  Arr [1] = 4  Arr [2] = 5  Arr [3] = 8  Arr [4] = 12  Arr [5] = 13  Arr [6] = 27  Arr [7] = 36  Arr [8] = 49  Arr [9] = 51    Enter an element to be searched in ascending array: 12  12 is available at position 6.

In the above program, we input all elements of an array in ascending order and then define a number as the target element is ’12’, which is searched from a sorted array using the binary search method. So, we create a user-defined function binary_search() that searches the defined element’s position from an array and returns the particular element available at this position. And if the element is not available in the sorted array, it returns 0.

Next TopicInheritance in C++ vs JAVA

Binary Search in C++

Binary Search in C++

Note: To perform a binary search technique in C++, a programmer or user should ensure the given array must be sorted either be in ascending or descending order.

Algorithm of the binary search in C++

Steps to perform the binary search in C++

State variable analysis: Examples with explanation

C++ Deque

You may also like