The binary search algorithm is widely used in programming. It requires that the array in which we search for the value to be sorted. So, we apply this search algorithm only on a sorted array. This algorithm is all about dividing in half (divide and conquer) until the element is found, or there are no more elements in the array to apply this mechanism.
Knowing our target number, we divide the array in half. If the searched number matches the item in the middle of the array, then the search is over. If the target is higher than the value from the middle of the array, then the search continues in the right side of the array, diving it again. This process continues repeatedly until we find the value or the array ends.
// Binary Search
#include <iostream>
using namespace std;
int binarySearch(int arrayOfNumbers[], int searchForNumber, int left, int right)
{
if (right >= left)
{
int middle = left + (right - left) / 2;
if (arrayOfNumbers[middle] == searchForNumber)
{
printf("The number %d is found at index %d", searchForNumber, middle);
return middle;
}
if (arrayOfNumbers[middle] > searchForNumber)
{
return binarySearch(arrayOfNumbers, searchForNumber, left, middle - 1);
}
return binarySearch(arrayOfNumbers, searchForNumber, middle + 1, right);
}
printf("The number %d was not found in the array", searchForNumber);
return -1;
}
int main(void)
{
int arrayOfNumbers[] = {1, 6, 9, 15, 17, 21, 30, 48, 61, 99};
int searchForNumber = 30;
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
int result = binarySearch(arrayOfNumbers, searchForNumber, 0, numberOfElements - 1);
}
Comments