Binary Search in C++ Standard Template Library (STL)

What is Binary Search?

Binary search is a popular type of algorithm which implements searches by sorting the arrays first before searching. Arrays can be defined as data types that store data points consecutively in sequential order. Binary search algorithm divide arrays into halves till all the elements are processed or the required element is detected. 

There are two types of binary search algorithms:

• Iterative Method
   
• Recursive Method

Binary Search Example

Here is an example of a binary search:

• C++

C++

#include<stdio.h>
int main()
{
   int c, first, last, middle, n, search, array[100];
   printf("Decide the the required amount of elements:\n");
   scanf("%d",&n); 
   printf("Choose %d integers:\n", n);
   for (c = 0; c < n; c++)
      scanf("%d",&array[c]); 
   printf("Decide a value you want to find:\n");
   scanf("%d", &search);
   first = 0;
   last = n - 1;
   middle = (first+last)/2;
   while (first <= last) {
      if (array[middle] < search)
         first = middle + 1;    
      else if (array[middle] == search) {
         printf("%d found in index %d.\n", search, middle+1);
         Break;
     }
      else
         last = middle - 1;
      middle = (first + last)/2;
   }
   if (first > last)
      printf("Failure! Unable to find %d. \n", search);
   return 0;  
}

You can also try this code with Online C++ Compiler

Run Code

Output 

Decide the required amount of elements:
8
 
Choose 8 integers:
5
15
29
37
41
53
67
71
 
Decide a value you want to find:
41
 
41 found in index 5.

You can also read about dynamic array in c.

Binary Search in C++ STL

Binary search in C++ is used to conduct one of the most fundamental operations to work on arrays. One of the methods to do this is traversing the array elements individually and checking to confirm if the required elements are present in the arrays.

In case the element is found, its present index is also mentioned and confirmed. Binary search is quite easy to apply and understand. It also opens up new paths into advanced searching and understanding of how arrays can be worked upon and manipulated. 

Binary search algorithms are more effective alternatives to linear search algorithms in terms of development time. Also, they are more complex while remaining limited. 

Using C++, one can write a binary search algorithm that helps in finding the required number or element from within a list of other integers. Using binary search, even the index or the position in the list of elements is figured out by the algorithm if, by chance, the entered element is found. Otherwise, it simply mentions that the system could not find the element in the list. 

To conduct a binary search in C++, the algorithms search the target values within a sorted array. The search can only be performed in a sorted array and must be in a descending or ascending order. Initially, the list of elements is split into halves, and then the target value is compared with the middle element of the sorted array.

The search is complete if there is a match, and the result is shown. In case it is not, the algorithm proceeds to search the array, which is the lower half of the elements are lesser than the element in the middle. If it is greater, then the search proceeds to the greater half of the array. These steps keep being repeated till the required element or target value is found. 

Must Read Recursive Binary Search.

How do you Program a Binary Search in C++ STL?

Here is how you program a binary search in C++ STL: 

A binary search example in C++:

• C++

C++

#include <iostream>
using namespace std;
 
int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;
 
    // If found at mid, then return it
    if (array[mid] == x)
      return mid;
 
    // Search the left half
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);
 
    // Search the right half
    return binarySearch(array, x, mid + 1, high);
  }
 
  return -1;
}
 
int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Unable to find");
  else
    printf("Observed in index %d", result);
}
 
#include<iostream>
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
      return mid ;
      if (arr[mid] > num)
      return binarySearch(arr, p, mid-1, num);
      if (arr[mid] > num)
      return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}
int main(void) {
   int arr[] = {3, 5, 7, 14, 27, 32, 43, 56, 62, 71};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int num = 43;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1)
   cout<< num <<" Unable to find";
   else
   cout<< num <<" Found at index "<< index <<" within the set of integers";
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

You can practice by yourself with the help of online c compiler.

Frequently Asked Questions

What is binary search in C++?

Binary search in C++ is writing codes using C++ to conduct searching algorithms that divide the total number of elements into two halves before starting the search.

What is binary search with an example?

A binary search is an algorithm for conducting searches that require a sorted array before applying a search.

Here is an example of a binary search using Python:

def binarySearch(array, x, low, high):
Repeat until the pointers low and high meet each other while low <= high: mid = low + (high – low)//2 if array[mid] == x: return mid elif array[mid] < x: low = mid + 1 else: high = mid – 1 return -1
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print(“Element is present at index ” + str(result))
else:
print(“Not found”)

You can also try this code with Online Python Compiler

Run Code

What is meant by binary search?

Binary search is a searching algorithm requiring sorting the arrays before searching.

How do you create a binary search tree in C++?

To create a binary search tree (BST) in C++, one needs to modify the TreeNode classes in the prior binary tree statements and build a binary tree ADT. Then, the Parent properties need to be integrated to track the parents of the nodes. Here is an example of how BST can be integrated:

class BSTNode
{
public:
int Key;
BSTNode * Left;
BSTNode * Right;
BSTNode * Parent;
};

Why do we need a binary search tree?

The main reason for using a binary search tree is that it extends the capabilities of normal arrays.

What is a binary search tree?

A binary search tree (BST) is implemented to conduct a binary search by following the various rules and being written based on these. The left child node’s value is lesser than the parent node's, and the right child node has a greater value than the parent node. Notably, all the nodes individually form a binary search tree.

What is a binary tree example?

Here is an example of writing a binary tree:

struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf(“%d \t”, root->key);
traversetree(root->right);
}
}
struct node* search(struct node* root, int key){
if (root == NULL || root->key == key)
return root;
if (root->key < key) return search(root->right, key);
return search(root->left, key);
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 33);
insert(root, 14);
insert(root, 11);
insert(root, 16);
insert(root, 33);
insert(root, 38);
insert(root, 46);
printf(“Here is the tree :\n”);
traversetree(root);
printf(“\nLooking for 11 within this tree “);
if(search(root , 11))
printf(“\nFound the required element”);
else
printf(“\nelement not found”);
return 0;
}

Here is the tree:
11 14 16 33 38 46
Looking for 11 within this tree
Found the required element

What is binary search in C?

Binary search is the application of binary search algorithms in C. It is another popular method of performing a search within arrays.

What are some applications of binary search?

Binary search can be applied using C++, C, .Net, PHP, and Java. During debugging, binary search is preferred for pinpointing the locations where errors are detected.

Conclusion

Binary search algorithms are a great way to learn how to conduct fundamental search functions using C++. Binary search in C++ is one of the popular ways of using these methodologies. One can use various programming languages to run a binary search but one of the best ways to apply and understand the functions of a binary search is through C++ STL. 

Recommended Readings:

• Dynamic Binding in C++

Recommended problems -

• Leaf Nodes in Binary Tree
• Vertical Order Traversal of a Binary Tree
• Binary Array Sorting

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles,  interview experiences, and interview bundle for placement preparations. Read our blogs on aptitude, competitive programming, interview questions, IT certifications, and data structures and algorithms for the best practice.