Category: Divide & Conquer

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 …

Exponential search

Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.

Interpolation search

Given a sorted array of integers and a target, find out if a target exists in the array or not. If target exists in the array, print index of it.

Binary Search

Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.

Inversion count of an array

Given an array, find the number of inversions of it. If (i < j) and (A[i] > A[j]) then the pair (i, j) is called an inversion of an array A. We need to count all such pairs in the array.