Binary search implementation in C++
The search algorithm known as binary Search is quicker than the linear search algorithm. Binary Search finds the target element's location in a sorted array by repeatedly halving the search space. With every comparison, binary Search removes half of the array. For this operation, the number of elements in the array is represented by the time complexity of O(log n).
How does a Binary Search operate?
The idea is to compare the target value and the middle element; if they are equal, the target value's position is indicated by the middle element's index.
The left half of the current space is searched for the target value if it is less than the middle element, and the right half is searched if the target value is greater than the middle element. This process is repeated if the element is present in the array until the target element is located.
Examples:
Input: nums[] = {18, 25, 37, 45, 53, 69, 72, 84, 97, 120, 156}, search = 97
Output: 8
Explanation: The element 97 is located at index 8
Input: nums[] = {18, 25, 37, 45, 53, 69, 72, 84, 97, 120, 156}, Search = 54
Output: -1
Explanation: The element 54 does not exist in the array nums[]
Recursive Binary Search in C++
//Implementing a recursive C++ program Binary Lookup
#include <bits/stdc++.h>
using namespace std;
// When elements are present
//The recursive Binary Search function returns -1
// otherwise, it finds the index of an
// element 'x' in a sorted array 'arr'.
// First: The index of the current sub-array first element
// last: The last element's index in the active sub-array
int binarySearch(int nums[], int first, int last, int search)
{
// Base case: The element is absent from the array
// if the search space is empty.
if (last >= first) {
// To split the search space in half
// determine the middle index.
int centre = first + (last - first) / 2;
// Provided that the middle element equals 'search'
// the element has been located; please return its index.
if (nums[centre] == search)
return centre;
// Proceed to search the left half of this array
// if the centre element has a higher value than 'search'.
if (nums[centre] > search)
return binarySearch(nums, first, centre - 1, search);
// Find the middle element in the right half of the array
// if it is less than 'search'.
return binarySearch(nums, centre + 1, last, search);
}
// Return -1 if the element is not in the array
// when the base case is reached.
return -1;
}
// Driver code
int main(void)
{
int nums[] = { 13, 24, 25, 36, 87};
int search = 36;
int x = sizeof(nums) / sizeof(nums[0]);
int final = binarySearch(nums, 0, x - 1, search);
(final == -1)
? cout << "The element is absent from the array."
: cout << "The element is found at index " << final;
return 0;
}
Output:
An Iterative C++ Binary Search Program
// C++ program to carry out
// iterative Binary Search
#include <bits/stdc++.h>
using namespace std;
// If an element is present,
//The Iterative Binary Search function returns -1; if not,
// it finds the index of element 'search' in a sorted array 'nums'.
//First: The index of the current
// sub-arrays first element
// last: The final element's index in
// the current sub-array
int binarySearch(int nums[], int first, int last, int search)
{
while (first <= last) {
int centre = first + (last - first) / 2;
// We have located the element if the middle element equals 'search';
//Please return its index.
if (nums[centre] == search)
return centre;
// Check the right half of the array for
// if the middle element is smaller than 'search'.
if (nums[centre] < search)
first = last + 1;
// If the middle element exceeds 'search',
//Look for it in the array's left half.
else
last = centre - 1;
}
// Return -1 if the base case is met and the element
// is not present in the array.
return -1;
}
// Driver code
int main(void)
{
int nums[]= { 43, 57, 87, 102, 120, 238 };
int search = 87;
int x = sizeof(nums) / sizeof(nums[0]);
int final = binarySearch(nums, 0, x - 1, search);
(final == -1)
? cout << "The element is absent from the array."
: cout << "The element is found at index " << final;
return 0;
}
Output:
