What is Binary Search?
Binary Search is a highly efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one.
How Binary Search Works
The steps of the binary search algorithm are as follows:
Initialize: Start with two pointers, left at the beginning and right at the end of the array.
Calculate Midpoint: Find the midpoint of the array.
Compare Midpoint: Compare the target value to the value at the midpoint.
If they are equal, you have found the target.
If the target is less than the midpoint value, move the right pointer to mid – 1.
If the target is greater than the midpoint value, move the left pointer to mid + 1.
Repeat: Repeat the process until left exceeds right.
Here is a simple Python implementation:
left, right = 0, len(arr) – 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid – 1
return –1
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search(arr, target)
if result != –1:
print(f“Element found at index {result}“)
else:
print(“Element not found in the array“)
Advantages of Binary Search
Efficiency: Binary search has a time complexity of O(log n), which is much faster than linear search, especially for large datasets.
Simplicity: The algorithm is straightforward and easy to implement.
When to Use Binary Search
Binary search is only applicable to sorted arrays or lists. If the data structure is not sorted, binary search will not work correctly.
Conclusion
Binary search is a powerful tool for quickly finding elements in a sorted array. Understanding and implementing binary search is a fundamental skill for any programmer. Try experimenting with the provided code and see how it works with different arrays and target values.
