🔹 Introduction
Binary Search is a powerful searching algorithm used on sorted arrays or lists. It repeatedly divides the search interval in half, making it extremely efficient — much faster than linear search for large datasets.
🔧 Python Code
pythonCopyEditdef binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Target found
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # Target not found
# Example usage
numbers = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(numbers, target)
print("Element found at index:", result)
🔍 Example
Input List:
[1, 3, 5, 7, 9, 11, 13, 15]
Target:7
Output:Element found at index: 3
📊 Time & Space Complexity
| Case | Time Complexity |
|---|---|
| Best | O(1) |
| Average | O(log n) |
| Worst | O(log n) |
- Space Complexity: O(1) (iterative version)
📖 Explanation
Binary search begins by checking the middle element of a sorted list:
- If it matches the target → success
- If the target is less, search the left half
- If the target is greater, search the right half
This divide-and-conquer approach makes binary search efficient — especially for large sorted datasets.
🌍 Real-World Usage
Binary Search is widely used in:
- Databases and index lookups
- Search engines
- Game AI (pathfinding/searching)
- Compiler optimization tables
It’s foundational in nearly every computing field where sorted data is present.
🏁 Final Thoughts
Binary Search is not just fast — it’s essential. Learning it helps you understand algorithmic efficiency and sets the stage for more advanced search algorithms like ternary search or interpolation search.
