The binary search is one of the fastest searching algorithms, which search a value in the sorted array in an O(logn) time complexity. Here we search a value using divide and conquer by repeatedly dividing the search interval in half. Problem statement: Given a sorted array X of n elements, search a given element key in X. If the key exists, then return its index in the sorted array. Otherwise, return -1.
There are two sorted arrays A and B of size n each, write a program to find the median of the array obtained after merging both the arrays(i.e., an array of length 2n which is even). The median of a sorted array of size n is defined as the middle element when n is odd and the average of the middle two elements when n is even.
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. This is an excellent matrix problem that can be solved in linear time complexity. The best part is — we are using the sorted order property and nested loops to improve the solution over the binary search approach.
We are given two integer arrays X and Y, write a program to check whether array Y is a subset of array X or not. An array Y is a subset of another array X if each Y element is present in X. How do you check if one array is a subset of another? Explore and Enjoy!
Given an array of integers sorted in ascending order, find the first and last position of a given value. This is a good interview problem to learn problem-solving using binary search.
You are given a row-wise sorted 2D matrix and a given integer k, write a program to find whether the integer ‘k’ is present in the matrix or not. The matrix has the following properties: Integers in each row are sorted from left to right and the first integer of each row is greater than the last integer of the previous row.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.