So far, we have seen that for each iteration, we are dividing the list by half and discarding one half completely for searching. This makes our list look like n/2, n/4, n/8, and so on after 1, 2, and 3 iterations, respectively. So, we can say that after Kth iteration, n/2^k items will be left. We can easily say that, the last iteration occurs when n/2^k = 1, or we can say that, 2^K = n. So, taking log from both side yields, k = log(n), which is the worst case running time for binary search algorithm. Here is the complexity for binary search algorithm:

If our array or list is already sorted, it is always preferred to apply binary search for better performance. Now, whether the list is sorted in the ascending order or descending order, it can have some impact on our calculation of low and high. The logic we have seen so far is for the ascending order. If an array is sorted in the descending order, the logic will be swapped where greater than will become less than, and vice versa. One thing to notice here is that the binary search algorithm provides us with the index we have found of the search item. However, there might be some cases where we not only need to know whether the number exists, but also to find the first appearance or last appearance in the list. If we use binary search algorithm, then it will return true or maximum index number, where the search algorithm found the number. However, it might not be the first appearance or last appearance. For that, we will modify the binary search algorithm a little, which we will call repetitive binary search tree algorithm.