A sorted array has been rotated (in one direction) for unknown number of times. Search a value in the array Note that, if the array was rotated exactly number of times equal to its length then its sorted again. So, we could have done a normal binary search on the sorted array. As the array […]
Tag Archives: binary search
Given an array of integer with duplicated elements. Find the first occurrence of a given number in the array. For example: A = [1, 1, 1, 2, 2, 3, 3, 3, 4]. So, first occurrence of 2 is in index 3, first occurrence of 4 is in index 8. The problem can be solved efficiently […]
Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of […]