The time complexity of binary search is O(log n) because it repeatedly divides the search interval in half. In contrast, linear search has a time complexity of O(n) as it scans each element one by one until the target is found or the end of the array is reached.
In depth
Binary search operates on a sorted array by comparing the target value to the middle element of the array. If the target is equal to the middle element, the search is complete. If the target is less, the search continues in the left half; if greater, it continues in the right half. This halving of the search space leads to a logarithmic time complexity, O(log n), because the number of elements to search through is reduced exponentially with each step. In contrast, linear search checks each element sequentially, resulting in O(n) time complexity, as every element must potentially be checked. Therefore, binary search is significantly more efficient for large datasets, provided the data is sorted beforehand.
Example scenario
In a production environment, consider an e-commerce application where users frequently search for products. When implementing a search function, using binary search on a pre-sorted list of product IDs can drastically reduce response times compared to a linear search, especially as the product catalog grows. For instance, searching for a specific product ID in a catalog of one million products with binary search would involve only about 20 comparisons, whereas a linear search could require up to one million comparisons in the worst case.
Common mistakes
One common mistake is to assume that binary search can be applied to unsorted data, which it cannot; the array must be sorted for binary search to work correctly. Another frequent error is misunderstanding how the logarithmic nature of binary search affects performance, leading to inflated expectations about its speed compared to linear search in smaller datasets, where linear search may actually perform well due to lower overhead.
Follow-up questions
- What would happen if the array is not sorted before applying binary search?
- Can you explain the space complexity of binary search?
- How would you implement binary search in a real-world application?
- What are some alternatives to binary search for different data structures?
Preparing for a system design interview?
- A 7-step method for answering any system design question, plus estimation numbers
- 5 worked designs: URL shortener, rate limiter, chat, news feed and file storage
- Guides to caching, databases, queues, consistency and reliability, with a 4-week study plan
- 306 practice questions with answers on caching, databases, queues, microservices, APIs and more
5 worked designs, a 4-week plan and 306 practice questions with answers.
The material stays free to read online. This is the organised, offline, print-ready PDF edition. Secure payment by PayPal; your personal download link is emailed after payment is confirmed. Digital product, no shipping.