In this tutorial, you will learn how the Binary Search sort works. Also, you will find working examples of Binary Search in Python.

Binary Search is a searching algorithm for finding an element’s position in a sorted array. In this approach, the element is always searched in the middle of a portion of an array. Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.

Working Principle:

  1. Select the middle element of the sorted collection.
  2. If the middle element matches the desired value, the search is successful.
  3. If the desired value is less than the middle element, discard the upper half of the collection.
  4. If the desired value is greater than the middle element, discard the lower half of the collection.
  5. Repeat the process on the remaining half until the value is found or the search interval becomes empty.

Binary Search Working

Binary Search Algorithm can be implemented in two ways which are discussed below.

  1. Iterative Method
  2. Recursive Method

The recursive method follows the divide and conquer approach. The general steps for both methods are discussed below.

  1. The array in which searching is to be performed is:
    initial array Binary Search

    Let x = 4 be the element to be searched.

  2. Set two pointers low and high at the lowest and the highest positions respectively.
    setting pointers Binary Search
  3. Find the middle element mid of the array ie. (arr[low + high]) / 2 = 6.
    mid element Binary Search
  4. If x == mid, then return mid.Else, compare the element to be searched with m.
  5. If x > mid, compare x with the middle element of the elements on the right side of mid. This is done by setting low to low = mid + 1.
  6. Else, compare x with the middle element of the elements on the left side of mid. This is done by setting high to high = mid - 1.
    finding mid element Binary Search
  7. Repeat steps 3 to 6 until low meets high.
    mid element Binary Search
  8. x = 4 is found.
    found Binary Search

Binary Search Algorithm

Iteration Method

Recursive Method

Python, Java, C/C++ Examples (Iterative Method)

Python, Java, C/C++ Examples (Recursive Method)

Key Advantages

  1. Efficiency: Binary search operates on sorted data, allowing it to discard half of the remaining elements at each iteration. This logarithmic time complexity (O(log n)) ensures quick retrieval even for large datasets.
  2. Versatility: Binary search can be applied to a wide range of data structures, including arrays, linked lists, and trees. As long as the collection is sorted, binary search can locate elements efficiently.
  3. Guaranteed Accuracy: Due to its divide-and-conquer nature, binary search guarantees accurate results. If the target element is present, the algorithm will find it, providing a sense of reliability in various applications.

Applications of Binary Search

  1. Searching in Databases: Binary search plays a vital role in database management systems, allowing for fast and efficient retrieval of records based on indexed attributes. It helps in optimizing search queries and improving overall performance.
  2. Spell Checking: In spell-checking algorithms, a sorted dictionary can be efficiently searched using binary search to suggest alternative word options based on user input, thereby improving the accuracy of spelling correction.
  3. Interval-based Problems: Binary search can be applied to solve interval-based problems, such as finding the intersection point between two intervals or identifying the first occurrence of a condition within a range.
  4. Lower and Upper Bound Queries: Binary search is useful for finding the lower and upper bounds of a value in a sorted collection, enabling various statistical calculations and optimization algorithms.

Binary search is a powerful algorithm that revolutionizes the efficiency of searching operations. Its elegance lies in the ability to divide the search space in half at each step, leading to faster and more accurate results. With its wide range of applications, binary search has become an indispensable tool in computer science and programming, aiding in solving complex problems and optimizing performance.

You may also like How to work Linear Search Algorithm, Feature & Example

Leave a Comment