In a sorted array, binary search is a searching technique that divides the search interval in half periodically. The goal behind binary search is to use the fact that the array is sorted to reduce the time complexity to O(log n).
Next, we will examine the fundamental steps in performing a Binary Search:
- Begin by creating an interval that spans the entire array.
- If the search key’s value is less than the item in the interval’s midpoint, you should narrow the gap to the lower half.
- On the off chance that is not the case, then we look for it in the upper half of our search space. We will repeatedly do these steps to a point where we find the value of our search space is empty.
In a nutshell, this search method takes advantage of a pre-sorted collection of objects by ignoring half of them after just one comparison. The step by step instructions include:
- Make a comparison between the target value to the middle element.
- We return the mid index if the target value matches the middle element.
- If the target’s value is more significant than the central element, you can find the target value in the right (greater) half subarray after the central element. The method is then applied to the right side.
- If the target value is smaller, the target value must be on the left (lower) part of the equation. As a result, the algorithm is applied to the left half.
Iterative Binary Search Program
It returns the index of the target value in the given array arr if present,
# It returns index of x in given array arr if present,
# else returns -1
def iterative_binary_search(arr, target):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# If target value is greater, ignore left half
if arr[mid] < target:
low = mid + 1
# If target value is smaller, ignore right half
elif arr[mid] > target:
high = mid - 1
# means the target value is present at mid
else:
return mid
# If we reach here, then the element was not present
return -1
# Test array
arr = [ 12, 13, 14, 10, 50 ]
target = 14
# Function call
result = binary_search(arr, target)
if result != -1:
print(" Target value is present at index::", str(result))
else:
print("Target value is not present in array::")
Recursive program for binary search
# Returns index of target in arr if present, else -1
def recursive_binary_search(arr, low, high, target):
# Check base case
if high >= low:
mid = (high + low) // 2
# returns the mid element if the target value is is
if arr[mid] == target:
return mid
# If the target element is smaller than mid value, then it can only
# be available in left subarray
elif arr[mid] > target:
return recursive_binary_search(arr, low, mid - 1, target)
# Else the target value can only be present in right subarray
else:
return recursive_binary_search(arr, mid + 1, high, target)
else:
# Element is not present in the array
return -1
# Test array
arr = [ 12, 13, 14, 20, 50 ]
target = 14
# Function call
result = binary_search(arr, 0, len(arr)-1, target)
if result != -1:
print("Target value is present at index::", str(result))
else:
print("Target value is not present in array::")
The preceding code snippet is similar to the one before it. A recursive function and its base condition are declared first. The lowest value must be less than or equal to the highest value. As in the last program, we calculate the middle number. Then, we used the while statement to continue with the binary search. The middle value is returned if it equals the number we are looking for.
If the median value has a value smaller than the target value, we use our recursive recursive_binary_search() function to increase the mid-value by one and assign it to low.
If the median value is higher than the value we’re looking for, we’ll use recursive_binary_search() to recursively decrease the mid-value by one and assign it to low. The only difference from the previous program is that we have supplied two parameters to the recursive_binary_search() function.
It is due to the recursive function’s inability to assign initial values to the low, high, and mid. The value for those variables will be reset every time the recursion is called. It will result in an incorrect result.
Complexities of Time
The search space is divided by two in each iteration. That means you have to deal with half of the previous iteration array in the current iteration. And the preceding stages are repeated until the beginning. The best-case scenario is when the initial mid-value matches the element to be searched.
- Best-case scenario complexity: O (1)
- Case complexity on average: O (log n)
- Complexity in the worst-case scenario: O(log n)
Space Complexity
The space complexity of the binary search method is determined by how the algorithm is implemented. Binary Search implementation does not necessitate the use of additional space. You can implement it in one of two ways:
Iterative approach
Looping conditions control the iterations in this method. In the iterative technique, the space complexity of the binary search is O. (1).
Recursive method
There is no loop in this function, and the new values are sent to the loop following recursion. The maximum and minimum values are used as the boundary conditions in this case. In the recursive technique, the space complexity of the binary search is O. (log n).
Applications for Binary Search
In a sorted array, it locates the position of an element
Beyond arrays, Binary Search has applications
- Determine whether n is the square root of an integer
- In a given array of sorted integers, find the first value larger than or equal to x.
- In an array of integers, find the frequency of a particular goal value.
- Rotate an already sorted array n times to find the peak of an array that climbs and then decreases. In the array, look for a target value.
Binary Search’s real-world applications
- Binary search is heavily used in the Dictionary
- Also, use binary search in debugging a linear piece of code to determine the location of the mistake
- Estimating the system’s resource requirements
- Locate values in a sorted set
- Test programs for semiconductors
- Mathematical solutions to a problem
- Java,.Net, and C++ STL libraries
Conclusion
Binary Search is a search algorithm responsible for determining an element’s position in a sorted array. The target element is always searched starting from the middle of a part of an array in this method. You can only use a sorted list of things for binary search. As a result, we must first sort the elements if they are not already sorted.
