Find the peak element in an array
Given an array, find the peak element in it. A peak element is an element that is greater than its neighbors. There might be multiple peak elements in an array, and the solution should report any peak element.
Category: Divide & Conquer
Find the number of 1’s in a sorted binary array
Given a sorted binary array, efficiently find the total number of 1’s in it.
Search in a nearly sorted array in logarithmic 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, search a given element in it efficiently. Report if the element is not present in the array.
Find floor and ceil of a number in a sorted integer array
Given a sorted integer array, find the floor and ceil of a given number in it. The floor and ceil map the given number to the largest previous or the smallest following integer.
Find the smallest missing element from a sorted array
Given a sorted array of distinct non-negative integers, find the smallest missing element in it.
Count occurrences of a number in a sorted array with duplicates
Given a sorted integer array containing duplicates, count occurrences of a given number. If the element is not found in the array, report that as well.
Find the first or last occurrence of a given number in a sorted array
Given a sorted integer array, find the index of a given number’s first or last occurrence. If the element is not present in the array, report that as well.
Search an element in a circularly sorted array
Given a circularly sorted integer array, search an element in it. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
Find the number of rotations in a circularly sorted array
Given a circularly sorted integer array, find the total number of times the array is rotated. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
Exponential search
Given a sorted array of n integers and a target value, determine if the target exists in the array or not in logarithmic time. If the target exists in the array, print an index of it.
Interpolation search
Given a sorted integer array and a target, determine if the target exists in the array or not using an interpolation search. If the target exists in the array, print an index of it.
Binary Search Algorithm – Iterative and Recursive Implementation
Given a sorted array of n integers and a target value, determine if the target exists in the array or not in logarithmic time using the binary search algorithm. If target exists in the array, print the index of it.