Sorting an array takes O(n log n) time. However, this time is still much less than O(n) time that would be taken by a linear search algorithm.
In order to narrow the search of an array down to half of the typical search time, the binary search can be used. It is a fast search algorithm with run-time complexity of Ο(log n). The binary search algorithm halves the search interval in each iteration by checking the mid-point of the search interval.
If the mid-point is the desired value, then the search is complete. If the mid-point is greater than the desired value, then the search interval is halved to the lower half and the search is repeated in that lower half. If the mid-point is less than the desired value, then the search interval is halved to the upper half and the search is repeated in that upper half.
This process is repeated until either the desired value is found or the search interval is empty. The binary search works on sorted arrays. Hence, if the array is unsorted, it needs to be sorted before the binary search can be applied to it.