Modified Binary Search

Consider the problem of determining whether a given element x is in array. To solve the search problem, there are many algorithms. And binary search is the most common search algorithm if the array is sorted. The number of comparisons performed by binary search on a sorted array of size n is at most ?? log n ?? +1. The time cost of binary search reaches the lower bound of the search problem. But in many circumstances, some information about the array before search is known. If the upper bound of the maximum difference between any adjacent elements in the array is known, one can design a preferable algorithm. It is referred as modified binary search. In the worst case, the maximum number of comparisons performed by modified binary search is between 1 and ?? log n ?? +1, obviously better than binary search.