| TOPIC: Binary Search | |
| DEFINITION: Binary search is an 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 the possible locations to just one. This approach solves the problem of quickly locating a specific element within a large sorted dataset. | |
| TIME_COMPLEXITY: The time complexity of binary search is O(log n), where n is the number of items in the list. This is because with each comparison, the algorithm effectively halves the search space, leading to a logarithmic number of steps. | |
| SPACE_COMPLEXITY: The space complexity is O(1), as binary search only requires a constant amount of additional space to store the indices and the target value, regardless of the size of the input list. | |
| USE_WHEN: Use binary search when you need to find an item in a large sorted list, and speed is crucial. This is particularly useful in scenarios where the list is too large to search linearly, and the data is already sorted or can be sorted efficiently. | |
| AVOID_WHEN: Avoid using binary search when the list is unsorted, as the algorithm relies on the data being sorted to work correctly. In such cases, a linear search or a different sorting algorithm followed by binary search might be more appropriate. | |
| EXAMPLE: | |
| Suppose we have a sorted list [2, 5, 8, 12, 16, 23] and we're looking for the number 12. | |
| Start with the entire list: [2, 5, 8, 12, 16, 23] | |
| -> Compare the middle element (8) with the target (12). Since 12 > 8, we know 12 must be in the right half. | |
| Narrow down to the right half: [12, 16, 23] | |
| -> Compare the middle element (16) with the target (12). Since 12 < 16, we know 12 must be in the left half of this subset. | |
| Narrow down further: [12] | |
| -> The only element left is 12, which matches our target: | |
| REAL_WORLD_ANALOGY: Binary search is similar to finding a specific book in a library where the books are arranged alphabetically by title. You start by looking at the middle shelf, then move to the left or right half depending on whether the book you're looking for comes before or after the middle book alphabetically, repeating this process until you find the book. | |
| SOURCE_NOTE: |