Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
What is C++ STL?
2.1.
Finding an element
2.2.
Lower bound
2.3.
Upper bound
3.
What is Binary Search?
3.1.
Binary Search Example
3.2.
C++
3.3.
Output 
4.
Binary Search in C++ STL
5.
How do you Program a Binary Search in C++ STL?
5.1.
C++
6.
Frequently Asked Questions
6.1.
What is binary search in C++?
6.2.
What is binary search with an example?
6.3.
What is meant by binary search?
6.4.
How do you create a binary search tree in C++?
6.5.
Why do we need a binary search tree?
6.6.
What is a binary search tree?
6.7.
What is a binary tree example?
6.8.
What is binary search in C?
6.9.
What are some applications of binary search?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

gp-icon
Basics of C++
Free guided path
9 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction 

Binary search, a highly efficient algorithm, demands prior sorting of the array for optimal performance. It operates by repeatedly dividing the search interval in half until the target element is found or the subarray becomes empty.

It is also one of the most fundamental operations that can be conducted to find a targeted value within a set of elements or integers. 

Introduction

What is C++ STL?

C++ STL is a very popular set of C++ template classes which provides various classes and functions with pre-installed templates, enabling the implementation of multiple common algorithms, models or data structures, such as vectors, queues, lists, and stacks.

In C++ language, there are mainly three types of operations which are performed using binary search :

1. Finding an element

2. Lower bound

3. Upper bound

Finding an element

Binary search is used to find the position of a specific element within a sorted array or container. The algorithm compares the target element with the middle element of the array. If the target element matches the middle element, the search is successful. If the target element is less than the middle element, the search continues on the lower half of the array; if the target element is greater, the search continues on the upper half. This process repeats until the element is found or the search space is exhausted.

Lower bound

The lower bound operation finds the position of the first element that is greater than or equal to a specified value (or key) in a sorted array or container. If the specified value is found in the array, the lower bound operation returns the position of the first occurrence of that value. If the value is not present, it returns the position of the first element that is greater than the specified value.

Upper bound

The upper bound operation finds the position of the first element that is greater than a specified value (or key) in a sorted array or container. If the specified value is found in the array, the upper bound operation returns the position immediately after the last occurrence of that value. If the value is not present, it returns the position of the first element that is greater than the specified value.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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; 
}

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 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”)

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, .NetPHP, 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:

 

Recommended problems -


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 aptitudecompetitive programminginterview questionsIT certifications, and data structures and algorithms for the best practice.

Previous article
Graph Implementation using STL
Next article
“Hello, World!” Program
Guided path
Free
gridgp-icon
Basics of C++
9 chapters
104+ Problems
gp-badge
Earn badges and level up
Live masterclass