We are going to explore the binary search algorithm in the C++ programming language. Binary search is a technique employed to locate specific elements within a sorted array by repeatedly dividing the array in half and searching for the desired elements in one of the halves. This process continues until a match is identified. Binary search operates effectively on 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++
The subsequent steps outline the procedure for executing the binary search algorithm 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: Initialize the variables and input all elements of a list in a specified order, either ascending or descending.
Step 2: Split the arrays' lists of elements into two equal halves.
Next, in Step 3, proceed to compare the target elements with the middle element within the array. If the value of the target element aligns with the middle element, then retrieve the position of the middle element and conclude the search operation.
If the desired element is smaller than the middle element, the search is focused on the lower half of the array.
If the specified element is greater in size than the middle element, the search operation should focus on the upper half of the array.
We will iterate through steps 4, 5, and 6 in a continuous loop until the specified element is no longer present in the sorted array.
Example 1: A code snippet to locate a particular value within an ordered array by employing the binary search algorithm.
Let's create a C++ program to locate a given number within a sorted array by implementing the binary search algorithm.
#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: Code for executing the binary search algorithm utilizing a custom 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 provided code snippet, we initialized an array named arr = {5, 10, 15, 20, 25, 30, 35, 40); and proceeded to look for the value '25' within this sorted array through the binary search technique. To accomplish this, we developed a custom function named binsearch to locate the specified number and output the message "Element is found at position 5". In case the number is absent within the array, the binsearch function will display "Element is not found in the array."
Example 3: Algorithm to locate the designated item through a recursive function
Let's generate an illustration to verify if the designated item exists within the ordered array by employing binary search within the recursive 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 preceding code snippet, we populate an array with elements in increasing order and designate '12' as the target element to be located within this sorted array using the binary search technique. Subsequently, a custom function named binary_search is crafted to pinpoint the position of the specified element within the array and retrieve the element located at that position. If the sought-after element is not present in the sorted array, the function returns 0.
