Binary Search
What is binary search?
Binary search is a common algorithm used in programming languages and programs. It can be helpful for technical interview questions. Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).
Advantages and Disadvantages?
In this paragraph, we will discuss some of the advantages of binary search. At each iteration, the binary search algorithm eliminates half of the list and significantly reduces the search space. It works even when the array is rotated by some position and finds the target element. It is better than a linear search algorithm since its run time complexity is O(logN).
Now, let’s see some disadvantages. Binary search is not good at handling duplicate items. While returning the first item, it might be possible we return a subsequence similar item. Also, there might be overflows in huge arrays when computing indices. Recursive vs non-recursive implementation, which should be considered while designing as recursive takes stack space.
Example of binary search
Binary Search Algorithm can be implemented in two methods: iterative and recursive method.
problem: let’s say you have an array and they want you to get the target.
nums = [2, 3, 5, 7, 8, 10, 12, 15, 18, 50, 77,90,100,110]
target = 8
First, to use the binary search you have to know if the array is sorted which is the case in this example. Here, the length of nums is 14. We have to find the number in the middle. 12 is in the middle. Since 12 is in the middle and is higher than the target value which is 8, we discard the right half and go left. Now, we have:
nums = [2, 3, 5, 7, 8,10]
target = 8
We do the same as before by getting the value in the middle. 5 is in the middle and is lower than the target. We discard the left half and go right. Now, we have
nums = [7, 8,10]
target = 8
As we do the same thing again, we get 8 in the middle which is also the target.
Iterative Implementation
# Function to determine if a `target` exists in the sorted list `nums`
# or not using a binary search algorithm
def binarySearch(nums, target):# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)# loop till the search space is exhausted
while left <= right:# find the mid-value in the search space and
# compares it with the targetmid = (left + right) // 2# target is found
if target == nums[mid]:
return mid# discard all elements in the right search space,
# including the middle element
elif target < nums[mid]:
right = mid - 1# discard all elements in the left search space,
# including the middle element
else:
left = mid + 1# `target` doesn't exist in the list
return -1if __name__ == '__main__':nums = [2, 3, 5, 7, 8, 10, 12, 15, 18, 50, 77,90,100,110]
target = 8index = binarySearch(nums, target)if index != -1:
print('Element found at index', index)
else:
print('Element found not in the list')
Thank you for reading my blog. Please follow me to read more about my journey. Hopefully, by my SHARING, YOU can IMPROVE as well.
