Introduction to Binary Search
What is Binary Search?
Binary search is a divide & conquer search algorithm used to find a specific element in a sorted array or list. It works by repeatedly dividing the search space in half until the target element is found or determined to be absent.
Binary search starts by comparing the target element with the middle element of the array. If they are equal, the search is complete. If the target element is smaller, the search continues on the lower half of the array; otherwise, it continues on the upper half.
This process is repeated until the target element is found or the search space is empty.
Binary Search Visualisation
What is a binary search?
What is the key difference between binary search and linear search?
Pros and Cons of Binary Search
Pros
- Efficient searching algorithm because it divides the search space in half with each comparison
- It can quickly find a desired element in a large data set
Cons
- Requires a sorted array, it cannot handle unsorted or unordered data
- Implementation is more complex than a linear search
Binary Search Python Implementation
Here is an example of Binary search python script. This script uses iteration (a loop), because the search function repeats its steps inside a while loop.
def binary_search(arr, target): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1 # Example usage array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] target = 23 result = binary_search(array, target) if result != -1: print("Element found at index", result) else: print("Element not found")
Recursive Binary Search
Binary search can also be written recursively: the function calls itself on the half of the list that could still hold the target. low and high mark the part still being searched.
def binary_search(arr, target, low, high):
if low > high: # base case: not found
return -1
mid = (low + high) // 2
if arr[mid] == target: # base case: found
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(array, 23, 0, len(array) - 1))5
There are two base cases, found and not found, so every chain of calls eventually stops.
In a recursive binary search, what happens when low becomes greater than high?
Tracing the Recursive Version
Each call works on a smaller range until a base case is reached. Searching for 23 in the list above:
Call low high mid arr[mid] Action 1 0 9 4 16 16 < 23, search right half 2 5 9 7 56 56 > 23, search left half 3 5 6 5 23 found, return 5
Call 3 returns 5 to call 2, which returns it to call 1, which returns it to the program. The iterative version makes the same comparisons inside a loop. It uses less memory, because it does not add a stack frame for every call.
Review: Fill in the Blanks
In binary search, the array is divided into two parts by finding the . The mid-point is the at the middle of the array. The target element is then compared with the element at the mid-point. If they are equal, the search is successful, and the index of the target element is returned. If the target element is smaller, the search continues on the left half of the array. Likewise, if the target element is larger, the search continues on the right half of the array.
Binary search has a of O(log n), where n is the size of the sorted array. This logarithmic time complexity arises from dividing the search space in half with each . Additionally, binary search has a of O(1), as it only needs a few variables to store the left and right boundaries as indices.
Complete! Ready to test your knowledge?
Binary Search Algorithm
- Introduction to Binary Search
- Binary Search Visualisation
- Pros and Cons of Binary Search
- Binary Search Python Implementation
- Recursive Binary Search
- Tracing the Recursive Version