Time complexity: At every step we divide the list using the same approach as in a normal binary search, hence the complexity is O(log(n)). Space complexity: There is no additional data structure created so the complexity is O(1)