# What is Binary Search

**Binary search**is a simple and efficient way to search for a specific item in a sorted list of items. Imagine you have a big phone book with names arranged alphabetically. Now, you want to find a particular name, let's say "Paddy."

Instead of flipping through every page one by one, binary search allows you to quickly narrow down your search by dividing the phone book in half. You open it to the middle and check the name. If the name you're looking for comes before the name on that page, you know it must be in the first half. If it comes after, you know it must be in the second half.

Let's say "Paddy" comes after the name on that page. You then repeat the process with the second half of the phone book, dividing it in half again and checking the name in the middle. You keep dividing the remaining portion until you find the name you're looking for or determine that it's not in the phone book at all.

Binary search works so efficiently because it eliminates half of the remaining options with each step. It's like playing a guessing game where you always split the remaining possibilities in half based on the information you have.

In computer programming, binary search is used to quickly find an item in a sorted array or list. It's a powerful algorithm that saves time and resources, especially when dealing with large amounts of data.

## Who invented it?

The binary search algorithm is attributed to a computer scientist named Dr. C. A. R. Hoare. He introduced this algorithm in 1960 while working on the development of the ALGOL programming language.

Dr. Hoare, also known as Tony Hoare, is a renowned British computer scientist who has made significant contributions to the field of computer science. He is widely recognized for his work in the areas of programming languages, operating systems, and software engineering. Binary search is one of his notable contributions, and it has become a fundamental algorithm used in various applications and programming languages.

## Pseudocode

```
function binarySearch(sortedList, target):
low = 0
high = length(sortedList) - 1
while low <= high:
mid = (low + high) / 2
if sortedList[mid] == target:
return mid // Found the target at index mid
if sortedList[mid] < target:
low = mid + 1 // Target is in the upper half
else:
high = mid - 1 // Target is in the lower half
return -1 // Target not found in the list
```

In this pseudocode, sortedList represents the sorted list of items in which we are searching, and target is the item we want to find. The algorithm begins by initializing low as the starting index of the list (0) and high as the ending index (length of the list minus 1).

The algorithm enters a while loop as long as low is less than or equal to high. Within the loop, it calculates the mid index as the average of low and high. It then compares the item at the mid index with the target.

If the mid item is equal to the target, the algorithm returns the mid index, indicating that the target has been found.

If the mid item is less than the target, the algorithm updates low to be mid + 1, indicating that the target must be in the upper half of the list.

If the mid item is greater than the target, the algorithm updates high to be mid - 1, indicating that the target must be in the lower half of the list.

If the loop completes without finding the target, the algorithm returns -1 to indicate that the target is not present in the list.

The algorithm enters a while loop as long as low is less than or equal to high. Within the loop, it calculates the mid index as the average of low and high. It then compares the item at the mid index with the target.

If the mid item is equal to the target, the algorithm returns the mid index, indicating that the target has been found.

If the mid item is less than the target, the algorithm updates low to be mid + 1, indicating that the target must be in the upper half of the list.

If the mid item is greater than the target, the algorithm updates high to be mid - 1, indicating that the target must be in the lower half of the list.

If the loop completes without finding the target, the algorithm returns -1 to indicate that the target is not present in the list.

## Sample Code

```
// C++ code snippet
int binarySearch(const vector
```& sortedList, int target) {
int low = 0;
int high = sortedList.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (sortedList[mid] == target) {
return mid; // Found the target at index mid
}
if (sortedList[mid] < target) {
low = mid + 1; // Target is in the upper half
} else {
high = mid - 1; // Target is in the lower half
}
}
return -1; // Target not found in the list
}
int main() {
// Sorted list of numbers
vector numbers = {2, 5, 7, 12, 16, 21, 28, 33};
int target = 16;
int index = binarySearch(numbers, target);
if (index != -1) {
cout << "Target " << target << " found at index " << index << endl;
} else {
cout << "Target " << target << " not found in the list" << endl;
}
return 0;
}

```
# Python code snippet
def binary_search(sorted_list, target):
low = 0
high = len(sorted_list) - 1
while low <= high:
mid = (low + high) // 2
if sorted_list[mid] == target:
return mid # Found the target at index mid
if sorted_list[mid] < target:
low = mid + 1 # Target is in the upper half
else:
high = mid - 1 # Target is in the lower half
return -1 # Target not found in the list
# Sorted list of numbers
numbers = [2, 5, 7, 12, 16, 21, 28, 33]
target = 16
index = binary_search(numbers, target)
if index != -1:
print(f"Target {target} found at index {index}")
else:
print(f"Target {target} not found in the list")
```

```
import java.util.Arrays;
public class BinarySearchExample {
public static int binarySearch(int[] sortedArray, int target) {
int low = 0;
int high = sortedArray.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (sortedArray[mid] == target) {
return mid; // Found the target at index mid
}
if (sortedArray[mid] < target) {
low = mid + 1; // Target is in the upper half
} else {
high = mid - 1; // Target is in the lower half
}
}
return -1; // Target not found in the array
}
public static void main(String[] args) {
int[] numbers = {2, 5, 7, 12, 16, 21, 28, 33};
int target = 16;
int index = binarySearch(numbers, target);
if (index != -1) {
System.out.println("Target " + target + " found at index " + index);
} else {
System.out.println("Target " + target + " not found in the array");
}
}
}
```

## Time and Space Complexity

The time complexity of the binary search algorithm is O(log n), where n represents the size of the sorted list or array. This means that the time it takes to perform a binary search grows logarithmically with the number of elements. Each comparison reduces the search space by half, resulting in a highly efficient search.

The space complexity of the binary search algorithm is O(1), which means it requires a constant amount of additional space regardless of the size of the input. Binary search does not require any significant additional memory beyond a few variables to keep track of the indices.

Both the time and space complexity of binary search make it highly efficient and suitable for searching in large sorted lists or arrays.

## Advantages

Efficiency: Binary search is highly efficient for searching in sorted lists or arrays. It reduces the search space by half with each comparison, resulting in a time complexity of O(log n), making it much faster than linear search (O(n)) for large datasets.

Optimal for Sorted Data: Binary search is specifically designed for searching in sorted data. It takes advantage of the sorted nature of the data to make quick decisions about which half of the remaining elements to search, leading to faster search times.

Versatility: Binary search is a general-purpose algorithm that can be applied to various scenarios beyond just searching for numbers. It can be used to search for specific elements, determine insertion points, find closest values, or perform other operations in a sorted list.

## Disadvantages

Requirement of Sorted Data: Binary search requires the input data to be sorted in ascending or descending order. If the data is not sorted, it either needs to be sorted first (which takes additional time) or a different search algorithm should be used.

Extra Space Not Utilized: Binary search does not take full advantage of the additional space available in modern data structures. It cannot leverage auxiliary data structures like hash tables or trees that provide more efficient searching and additional operations.

Limited Applicability: Binary search is not suitable for unsorted or dynamically changing data. If the data frequently changes or needs to be searched in an unsorted manner, binary search becomes less effective. Other algorithms like linear search or hash-based search might be more appropriate.