# Category: Divide & Conquer

## Maximum Sum Subarray using Divide & Conquer

Given an array of integers, find maximum sum subarray among all subarrays possible. Get great deals at Amazon

## Find peak element in an array

Given an array, find peak element in it. A peak element is an element that is greater than its neighbors.

## Find number of 1’s in a sorted binary array

Given a sorted binary array, efficiently find the number of 1’s in it.

## Search in a nearly sorted array in log(n) 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.

## Find Floor and Ceil of a number in a sorted array

Given a sorted array of integers, find 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, respectively.

## Find smallest missing element from a sorted array

Given a sorted array of distinct non-negative integers, find smallest missing element in it.

## Count occurrences of a number in a sorted array with duplicates

Given a sorted array of integers containing duplicates, count occurrences of a number provided. If the element is not found in the array, report that as well.

## Find first or last occurrence of a given number in a sorted array

Given a sorted array of integers, find index of first or last occurrence of a given number. If the element is not found in the array, report that as well.

## Search an element in a circular sorted array

Given a circular sorted array of integers, search an element in it. Assume there are no duplicates in the array and the rotation is in anti-clockwise direction.

## Find number of rotations in a circularly sorted array

Given a circularly sorted array of integers, find the number of times the array is rotated. Assume there are no duplicates in the array and the rotation is in anti-clockwise direction.

## 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 using interpolation search. If target exists in the array, print index of it.