So now, we are in a situation where we have an array with n items and they are not sorted. Since we know binary search is faster, we have decided to sort it first and then search for the item using a binary search. If we do so, we have to remember that the best sorting algorithms have a worst time complexity of O(nlog n), and for binary search, the worst case complexity is O(log n). So, if we sort and then apply the binary search, the complexity will be O(n log n) as it is the biggest one compared to O(log n). However, we also know that for any linear or sequential search (sorted or unsorted), the worst time complexity is O(n), which is much better than O(n log n). Based on the complexity comparison of O(n) and O(n log n), we can clearly say that performing a linear search is a better option if the array is not sorted.

Let's consider another situation where we need to search a given array a multiple number of times. Let's denote k as the number of times we want to search the array. If k is 1, then we can easily apply our linear approach discussed in the last paragraph. It will be fine if the value of k is smaller compared to the size of the array, which is denoted by n. However, if the value of k is closer or bigger than n, then we have some problems applying the linear approach here.

Let's assume that k = n, then for n time, linear search will have a complexity of O(n²). Now, if we go for the sort and then search option then even if k is bigger, the onetime sorting will take O(n log n) time complexity. Then, each search will take O(log n), and n times searching will have a worst case of O(n log n) complexity. If we take the worst running case here, we will have O(n log n) for sorting and searching k items, which is better than sequential searching.

So, we can come to the conclusion that if a number of search operations is smaller compared to the size of the array, it is better not to sort the array and perform the sequential search. However, if the number of search operation is bigger compared to the size of array, it is better to sort the array first and then apply the binary search.

Over the years, the binary search algorithm evolved and came up with different variations. Instead of choosing the middle index every time, we can make calculative decisions to choose which index we should use next. That is what makes these variations work efficiently. We will now talk about two such variations of binary search algorithm: interpolation search and exponential search.