Algorithm explanation: based on an unsorted list I want to find the indexes of the values in another sorted list. Note that all values are unique and the two lists have the same values, only in different order, for example:
# O(log n) def binary_search(data, value): n = len(data) left = 0 right = n - 1 while left <= right: middle = (left + right) / 2 if value < data[middle]: right = middle - 1 elif value > data[middle]: left = middle + 1 else: return middle raise ValueError('Value is not in the list') # O(n log n) def find_indexes(data1, data2): return [binary_search(data2, value) for value in data1] if __name__ == '__main__': data1 = [9, 1, 8, 2] data2 = [1, 2, 8, 9] print(find_indexes(data1, data2)) # >> [3, 0, 2, 1]
Can someone please confirm that the function
find_indexes has quasilinear time complexity?
Note that this is not a real problem and I'm not trying to improve this algorithm. I'm just trying to exemplify how a quasilinear algorithm works in a simple way.