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
The main advantage of binary search lies in its significant reduction of the search space with each iteration. This allows for a fast search process, resulting in a logarithmic of O(log n), where n represents the size of the array. The of binary search is relatively low with O(1), as it only requires a small amount of additional space to store the mid-point index and the comparison result.
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