Binary search is a fast and efficient algorithm used to locate an item in a sorted list by repeatedly dividing the search range in half.
What is binary search?
Binary search is a widely-used algorithm that is significantly more efficient than linear search for finding items in an ordered list. Instead of checking each element one by one, it reduces the number of possibilities by half at every step, narrowing down the potential position of the desired element until it is either found or confirmed to be absent. This makes binary search especially useful in situations involving large data sets, where performance and speed are important.
Binary search works only on lists that are already sorted in a specific order, usually in ascending order. If the list is unsorted, the binary search will not work properly and may return incorrect results. The algorithm is based on the principle of divide and conquer, meaning it breaks the problem into smaller parts and solves each part to reach the overall goal.
Prerequisite: list must be sorted
A sorted list is a critical requirement for binary search to operate correctly. The algorithm assumes that the elements follow a defined order—most commonly ascending. Without this order, the binary search has no basis for determining which half of the list to ignore after comparing the middle value with the target.
Practice Questions
FAQ
Integer division is used to calculate the midpoint to ensure the result is a whole number, corresponding to a valid index in the list. In binary search, the midpoint is found using the formula (start + end) // 2. This prevents index errors and avoids accessing invalid positions in the list. However, a potential issue arises when working with very large lists where start + end could exceed the maximum integer size supported by the system, especially in older programming languages or constrained environments. This could lead to an integer overflow, causing incorrect midpoints or crashing the program. To prevent this, a safer method is to use start + (end - start) // 2, which avoids adding two potentially large numbers together. Although most high-level languages like Python handle large integers gracefully, understanding this issue is important when writing performance-critical or low-level code, such as in C or Java on memory-limited systems.
Standard binary search will only return one occurrence of the target value in a sorted list, and not necessarily the first or last. To find all occurrences of a duplicate value, the algorithm must be modified. First, perform a binary search to locate any instance of the value. Once found, expand outward from that index—checking adjacent elements on both the left and right—until the values no longer match the target. Alternatively, more efficient methods involve two modified binary searches: one to find the first occurrence by continuing to search in the left half even after a match is found, and one to find the last occurrence by searching the right half after a match. Once both indices are known, all positions in between can be collected. This approach maintains the efficiency of binary search and avoids scanning the entire list unnecessarily, making it far better than linear search for finding duplicates in large sorted datasets.
If binary search is applied to a list sorted in descending order using the standard algorithm designed for ascending order, it will not work correctly. The logic of moving left or right based on comparisons assumes ascending order, so it would incorrectly discard the half of the list that actually contains the target. To perform binary search on a descending list, the comparison logic must be reversed. Specifically, if the target is less than the midpoint value, the search should proceed to the right half; if the target is greater, it should go to the left half. This is the opposite of what is done in an ascending list. The rest of the algorithm remains the same, including the way the midpoint is calculated. It is essential to adjust the logic accordingly; otherwise, the search will either return incorrect results or fail to find the target even if it exists in the list.
Yes, binary search can be applied to non-numerical data types such as strings or objects, provided that the data is sorted according to a well-defined ordering. For strings, the ordering is usually lexicographical (dictionary order), where "apple" comes before "banana", and so on. The algorithm then compares strings using relational operators (e.g. <, ==, >). For objects, binary search can be used if a custom comparison method is defined—often using attributes within the object that are ordered. For example, if each object represents a student and you want to search based on student ID, you must ensure that the list is sorted by ID and comparisons are based on that attribute. Languages like Python allow defining comparison methods (__lt__, eq, etc.) within classes to make this possible. It’s important to maintain consistency in sorting and comparison logic; otherwise, binary search may yield unpredictable or incorrect results.
Binary search functions correctly regardless of whether the list has an even or odd number of elements. When a list has an even number of elements, there is no single central value, so the algorithm typically selects the lower or upper of the two middle indices depending on how the midpoint is calculated. Using the formula (start + end) // 2, the integer division will automatically select the lower of the two middle indices. For example, in a list of 6 elements with indices 0 to 5, (0 + 5) // 2 yields 2. This choice is consistent and ensures that the algorithm continues to reduce the search space correctly. Whether the midpoint is biased towards the lower or upper middle element doesn't affect the algorithm's correctness, as long as the implementation is consistent and the comparison logic is sound. However, understanding this detail is useful when debugging or implementing variations of the binary search algorithm.
