Binary Search — A Recursive way of searching

Binary search is a search algorithm where we divide the given set of elements from the middle and compare the element to be searched with the element in the middle. If the element is smaller than the middle, we repeat the process in the first half of the dataset otherwise in the second half until the element to be searched is equal to the middle element.

Algorithm

binarySearch(int[] arr, int key, int low, int high) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (key == arr[mid]) {
return mid;
} else if (key > arr[mid]) {
return binarySearch(arr, key, mid + 1, high);
} else {
return binarySearch(arr, key, low, mid - 1);
}
}

Time & Space Complexity

Binary search follows a divide and conquer technique.

Usage & Benefits

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store