Today was a bit busy day but I did learn an algorithm. This algorithm is called Binary Search which is a searching algorithm that recursively searches for a given element in a list.
Binary Search
Binary Search or also called Lograthimic search is a searching algorithm that find the given element in a sorted array. This list much be sorted for Binary search to work correctly. Binary Search is recursive alogorithm. But how it works?
How Binary Search Works?
Binary search takes two inputs, a sorted list and the element to look for in the list. Let this number be X. The algorithm will first compare the middle element from the list with X. If you are lucky and the middle element is the one you are looking for, the loop will end and the function will return X but that is not always the case and so the algorithm will check if the number is bigger or smaller than X.
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
X = 2
quick_sort(nums, X)
If the middle element is smaller than X the algorith will look in the left half of the list and if the X is bigger then it will look for in the right half of the list and goes on recursively until it finds the element.
Implementation
def binary_search(arr, num):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# calculate mid point of the list
if list1[mid] < num:
low = mid + 1
elif list1[mid] > num:
high = mid - 1
else:
return mid
return
list1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
num = 2
result = binary_search(list1, num)
if result:
print(f"At index: {result}")
else:
print(f"Num not in list")
This will print out the result At index: 1 because the number 2 is at position 1 starting from 0.
zainsci