“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 other

## Visualizing 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 -1

## Complexity 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!!