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");
}
}
}