“I learned very early the difference between knowing the name of something and knowing something.”
― Richard P. Feynman
These blog series capture the essence of Feynman’s quote, emphasizing the distinction between superficial knowledge (knowing the name of something) and deep understanding (knowing something). If you want to learn beyond the name of Binary Search then read away 😊
Introduction: Binary Search
- Binary search is a search algorithm.
- It works on a sorted array.
- It is based on the principle of Divide and Conquer.
Thought Process
Consider a book of 100 pages and you have to go to page 50. Initially, you open the book on some random page number, say 60. Now you compare whether the current page number is greater than or smaller than 50. Based on that you either search in the first half of the book (if 50 < current page i.e. 60) or the last half of the book (if 50 > current page i.e. 60). And you repeat this process until you land on page 50!
Algorithm
1. Given an array of sorted number and an element to search in that array
2. Initialize search area as whole array with startIndex=0 and endIndex=last index of array
3. Calculate the mid index between these two points
4. Compare the mid index element (MiddleElement) with the searched element
a. If the searched element is found, return mid index
b. If searched element is smaller, initialize new search area (first part of array) with startIndex=0 and endIndex=midIndex-1
c. If searched element is larger, initialize new search area (last part of array) with startIndex=midIndex+1 and endIndex=last index of array
5. Continue searching the element till the element is found or your startIndex and endIndex cross each otherVisualizing Binary Search in Action
Pseudo Code for Binary Search
BINARY-SEARCH(element,arr)
low = arr[0]
high = arr.length - 1
while low < high
mid = (low+high)/2
if element == arr[mid]
return mid
if element < arr[mid]
high = mid-1
else
low = mid+1
return -1Complexity of Binary Search
- Binary Search works in O(logN) complexity
Java Implementation
class BinarySearch {
public int binarySearchIterative(int arr[], int element){
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == element){
return mid;
}else if (arr[mid] < element){
low = mid + 1;
}else{
high = mid - 1;
}
}
return -1;
}
public int binarySearchRecursive(int arr[], int low, int high, int element){
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == element){
return mid;
}
if (arr[mid] > element){
return binarySearchRecursive(arr,low, mid - 1, element);
}
return binarySearchRecursive(arr, mid + 1, high, element);
}
return -1;
}
public static void main(String args[]){
BinarySearch searchObj = new BinarySearch();
int arr[] = { 10,20,30,40,50,60 };
int index = searchObj.binarySearchIterative(arr, 20);
if (index == -1){
System.out.println("Element is not present in the array");
}else{
System.out.println("Element is present at index " + index);
}
index = searchObj.binarySearchRecursive(arr,0 , arr.length-1, 50);
if (index == -1){
System.out.println("Element is not present in the array");
}else{
System.out.println("Element is present at index " + index);
}
}
}Food for Thought 💡
To initialize the mid index, the following two approaches can be seen in different places:
However, the second approach fails when the low and high addition leads to a value that cannot be accommodated in int. In order to avoid integer overflow, the first option is preferred.
Thank you for giving me the gift of your precious time 😇 Happy Reading!!
