Find kth smallest value in a sorted matrix
Given a row-wise and column-wise sorted square matrix and a positive integer k, find the kth smallest number in the matrix.
Tag: Binary Search
Find `k` closest elements to a given value in an array
Given a sorted integer array, find the k closest elements to x in the array where k and x are given positive integers.
Check if a number is a perfect square
Given a positive number, check if it is a perfect square without using any built-in library function. A perfect square is a number that is the square of an integer.
Find the square root of a number using a binary search
Given a positive number, find the square root of it. If the number is not a perfect square, then return the floor of its square root.
Unbounded Binary Search
Given a monotonically increasing function f(x) on the non-negative integers, find the value of x, where f(x) becomes positive for the first time. In other words, find a positive integer x such that f(x-1), f(x-2), … are negative and f(x+1), f(x+2), … are positive.
Find the odd occurring element in an array in logarithmic time
Given an array of n integers where every element appears an even number of times except one element, which appears an odd number of times, find that odd occurring element in logarithmic time and constant space.
Find the missing term in a sequence in logarithmic time
Given a sequence of n numbers such that the difference between the consecutive terms is constant, find the missing term in logarithmic time.
Division of two numbers using binary search algorithm
This post will discuss the division of two numbers (integer or decimal) using the binary search algorithm.
Find floor and ceil of a number in a sorted array (Recursive solution)
Given a sorted integer array, find the floor and ceiling of a given number in it. The floor and ceiling map the given number to the largest previous or the smallest following integer.
Find pairs with difference `k` in an array | Constant Space Solution
Given an unsorted integer array, find all pairs with a given difference k in it without using any extra space.
Find the frequency of each element in a sorted array containing duplicates
Given a sorted array containing duplicates, efficiently find each element’s frequency without traversing the whole array.
Ternary Search vs Binary search
In this article, we will implement a ternary search algorithm and compare its performance with binary search algorithm.