Table of Contents
Introduction
Binary search in C++ is a great way to experiment with the binary search algorithm to program searching applications using C++ Standard Template Library (C++ STL). It is a compact and valuable methodology that helps budding programmers and developers write and work with more complex and advanced applications in the future. 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.
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.
Wish to build a bright future in Coding? Enroll in our Premium Courses!
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 algorithms 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 binary search:
#include
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 Example:
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.
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, the index it is present in is also mentioned and confirmed. Binary search is quite easy to apply and understand. It also opens up new paths into advanced searching and the 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 which 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.
If there is a match, then the search is complete 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.
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++:
#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;
Preparing for Product-Based Companies? Check Out Must Do Coding Questions for Product Based Companies
Frequently Asked Questions
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.
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”)
Binary search is a searching algorithm requiring the sorting of the arrays before searching.
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 for tracking 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;
};
The main reason for using a binary search tree is due to it extending the capabilities of normal arrays.
A binary search tree (BST) is a tree 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 that of the parent node and the right child node has a greater value than the parent node. Notably, all the nodes individually form a binary search tree.
Here is an example of writing a binary tree:
include
include
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
Binary search is the application of binary search algorithms in C. It is another popular method of performing a search within arrays.
Key Takeaways
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.
We have launched a new Preparation Guide for your next interview.
One can gather a lot of working knowledge and result-based experience from programming a binary search on his/her own and improvising on the different aspects and parameters. This also helps gather a deep understanding of how arrays work and how to work with more advanced applications.
