Tag: Binary Search

Search in a nearly sorted array in O(logn) time

Given a nearly sorted array such that each of the N elements may be misplaced by no more than one position from the correct sorted order, efficiently search a given element in it. Report if the element is not present in the input array.   An element at index i in correct sorted order can …