For any queries you can reach us at / WhatsApp us: +919158876092

Binary Search in Data Structures - Infovistar

Binary Search

A binary search algorithm finds the position of the target element in a sorted array. It compares the target element with the middle element of the array.

Binary search exhibits better timing behaviour for large volume of data with timing complexity O(log2n)

Binary search is a search technique that works efficiently on sorted lists.

Binary search uses the divide and conquer strategy, in which the list is divided into two halves, with the item being compared with the middle element of the list.

If a match is found, the location of the middle element is returned. Otherwise, we search into either of the halves depending on the result produced through the match.

Binary Search

Time Complexity

Case Time Complexity
Best Case O(1)
Average Case O(log n)
Worst Case O(log n)
  • Best Case O(1): It occurs when the element to be search is found in first comparison. That is the first middle element itself is the element to be searched
  • Average Case O(log n): Binary search has an average case time complexity of O(log n)
  • Worst Case O(log n): The worst case occurs in Binary search when we have to keep reducing the search space until it contains only one element.

The binary search has a time complexity of O(long n)

Space Complexity

The binary search has a space complexity of O(1).