Notes on binary search
Binary search is a essential algorithm used in coding interview. It is used to search for an target element x in a sorted list a: list with a time complexity O(log(n)). The naive way to search for x in a is to iterate through the list and check if a[i] == x for every i in range(len(a)). The time complexity of such an naive approach is O(n). However, if the list is not sorted, we can sort it first sort it first with a time complexity of O(nlog(n)) and then followed by a binary search....