Binary search

« Back to Glossary Index

Binary search is an efficient algorithm for locating an element in a sorted dataset.
It works by repeatedly dividing the search space in half:

1. Check the middle element.
2. If it matches the target → stop.
3. If the target is smaller → continue on the left half.
4. If the target is larger → continue on the right half.

The average complexity is O(log n), much faster than a sequential search (O(n)).

---

In the context of Relational Databases

• Binary search principles underpin index structures such as B-Trees and B+Trees.
• When a table has an index (e.g., on a primary key), the DBMS doesn’t scan all rows; it “jumps” through the index using a binary search–like process.
• Example: SELECT * FROM Clients WHERE id_client = 1050 in a table with millions of rows is resolved efficiently thanks to this mechanism.

---

Simple example

Dataset:

[ 2, 5, 9, 14, 20, 33, 41, 57 ]

Search for 20:

• Middle element is 14.
• 20 > 14 → search right half.
• New subset: [20, 33, 41, 57].
• Middle element is 33.
• 20 < 33 → search left half.
• Found 20. ✔

« Back to Glossary Index