What is binary search algorithm?
Well, it's an algorithm :)
An algorithm is a set of finite instructions or rules used to solve a particular problem. A binary search algorithm takes a sorted input of a list of elements, such as numbers. When the element you are searching for is in the list, the algorithm returns where it is located.
Why use Binary Search?
Binary search is well suited for a large input of elements.It is more efficient than a linear search where a case of say 1024 elements would take 1023 steps (worst case) or so to get an element near the 1024 mark. A binary search would take log n time to get an element from the same(worst case). log 1024 = 10 this means it would take 10 steps since 2 to the power of 10 is 1024. Simply log n here means logarithmic time and it's computed as log n to the base of 2 in layman's terms think of it as "How many 2s do we multiply together to get 1024?"
The time is shortened quite impressively right?
Now let's see how it works
The code here is in Python, but the logic is the same for other programming languages. Okay, so binary search works only with a sorted list and you'll keep track of the part of the list to search through, at first it's the entire array:
low = 0
high = len(list) - 1
Each time you check the middle element;
mid = (low + high) / 2
guess = list[mid]
Here your guess is that just maybe the element you are searching for is in the middle of your list, if the guess is too low, you'll adjust low accordingly:
low = mid + 1
And if the guess is to high, you update high; Here is the full python code
"""binary search"""
def binary_search(list: [int], num: int) -> int:
"""num is the searched number in the list"""
low = 0
high = len(list) - 1
list.sort() # sort the list
while(low <= high):
# get the middle element
mid = (low + high) // 2
guess = list[mid]
if guess == num:
return mid
if guess > num:
high = mid - 1
else:
low = mid + 1
return 0
if __name__ == '__main__':
number_to_search = 5
list = [1,8,9,3,4,6,5,10,7]
print(binary_search(list, number_to_search))
The code returns 3 which is the position of 5 in the 0-based index of the sorted list.
You can try out the code with larger inputs and see the beauty of it. Alright that's it, Happy Coding!
Top comments (0)