Binary Search

Binary search is an efficient searching algorithm that works on sorted data. Instead of checking every element one by one, it repeatedly divides the search area in half, quickly narrowing down the location of the target value.

---

Prerequisite: The Data Must Be Sorted

Binary search only works on sorted data (either ascending or descending order). If the data is unsorted, you must sort it first before applying binary search, or use linear search instead.

---

How Binary Search Works

1. Find the middle element of the list.
2. Compare the middle element with the target value.
3. If the middle element equals the target, the search is complete — return its position.
4. If the target is less than the middle element, discard the right half and repeat on the left half.
5. If the target is greater than the middle element, discard the left half and repeat on the right half.
6. Repeat until the target is found or the search area is empty (the target is not in the list).

---

Pseudocode for Binary Search