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:
- Select the middle element of the sorted collection.
- If the middle element matches the desired value, the search is successful.
- If the desired value is less than the middle element, discard the upper half of the collection.
- If the desired value is greater than the middle element, discard the lower half of the collection.
- 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.
- Iterative Method
- Recursive Method
The recursive method follows the divide and conquer approach. The general steps for both methods are discussed below.
- The array in which searching is to be performed is:
LetÂ
x = 4Â be the element to be searched. - Set two pointers low and high at the lowest and the highest positions respectively.
- Find the middle element mid of the array ie.Â
(arr[low + high]) / 2 = 6. - If x == mid, then return mid.Else, compare the element to be searched with m.
- 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. - 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. - Repeat steps 3 to 6 until low meets high.
x = 4Â is found.
Binary Search Algorithm
Iteration Method
1 2 3 4 5 6 7 8 9 10 | do until the pointers low and high meet each other. mid = (low + high)/2 if (x == arr[mid]) return mid else if (x > A[mid]) // x is on the right side low = mid + 1 else // x is on the left side high = mid - 1 |
Recursive Method
1 2 3 4 5 6 7 8 9 10 11 12 13 | binarySearch(arr, x, low, high) if low > high return False else mid = (low + high) / 2 if x == arr[mid] return mid else if x < data[mid] // x is on the right side return binarySearch(arr, x, mid + 1, high) else // x is on the right side return binarySearch(arr, x, low, mid - 1) |
Python, Java, C/C++ Examples (Iterative Method)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array[mid] == x: return mid elif array[mid] < x: low = mid + 1 else: high = mid - 1 return -1 array = [3, 4, 5, 6, 7, 8, 9] x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found") |
Python, Java, C/C++ Examples (Recursive Method)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | # Binary Search in python def binarySearch(array, x, low, high): if high >= low: mid = low + (high - low)//2 # If found at mid, then return it if array[mid] == x: return mid # Search the left half elif array[mid] > x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = [3, 4, 5, 6, 7, 8, 9] x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found") |
Key Advantages
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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