Let's understand first what would be the best way to implement search algorithm when first half of array is sorted and second half is unsorted.
Approach would be to apply binary search for first half and see if we are successful in finding element we are searching for. Thus giving us results with O(logn) time complexity.
Now if element is not found in first half of the sorted part, we can apply linear search on second half which is unsorted array which will give us O(n) time complexity.
So in worse case, element may be found in second half in unsorted array and to reach here, we would have already used binary search for first half.
This will give us time complexity = O(logn) + O(n)
Now when we talk about asymptotic time complexity, we always consider very large input size of n and because of this, O(n) ยป O(logn)
so O(logn) + O(n) = O(n)
You might think what if we apply binary search on entire array where first half is sorted and second half is unsorted? You might get wrong results if element is not found in sorted part because for unsorted part, binary search may give wrong results because it uses order of elements to narrow down its search space in each step.
