What does a binary search algorithm operate on?

A binary search algorithm operates on sorted lists. The fundamental principle behind binary search is its method of dividing a sorted list into halves to efficiently locate a target value. Starting with the middle element of the list, the algorithm compares the target value to this middle element. If the target value is equal to the middle element, the search is successful. If the target value is less than the middle element, the search continues in the lower half of the list; if it is greater, the search continues in the upper half.

This division process leverages the order of the list, allowing the algorithm to eliminate half of the remaining elements from consideration with each comparison, resulting in a time complexity of O(log n). In contrast, unsorted lists would not allow for such efficient searching because there would be no guaranteed order to leverage, making it necessary to examine each element individually. Random data lacks the organized structure required for a binary search, and while linked lists can be sorted, the inherent nature of linked lists often makes them less efficient for random access, which is a key step in binary search. Hence, binary search is specifically tailored for sorted lists.