Write a program that returns a fixed point in the given sorted array of distinct integers. A fixed point is an index i such that X[i] = i. If a fixed point exists, the program should return the index of the fixed point. If no fixed point is found, the program should return -1. Note that the integers in the array can be both positive and negative.
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.
Given an array of integers sorted in ascending order, write a program to find the first and last occurrence of a given element. Our goal should be to design an algorithm with O(log n) time complexity. Note: This is an excellent question to learn problem-solving using binary search. Here we need to apply binary search twice to solve this problem.
Given two unsorted arrays of size m and n, find whether one array is a subset of another array or not. An array Y will be a subset of another array X if each element of Y is present in X. Assume that there are no repeated elements in both arrays and n <= m. Note: This is an excellent problem to learn problem solving using various approaches.
There are two sorted arrays A and B of size n each, write a program to find the median of these two sorted arrays obtained after merging (new merged array will be 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.
You have given row-wise and column-wise sorted 2d matrix and integer k, write a program to search k in 2d matrix, i.e. find whether k is present or not. Each row is sorted from left to right, and the first integer of each row is greater than the last integer of the previous row. Note: This is an excellent problem to learn problem solving binary search in a 2d matrix.
You are given an array of n integers that is first increasing and then decreasing. Write a program to find the maximum value in the array. Our goal should be to solve this problem using O(logn) time complexity. Note: This is an excellent problem to learn problem solving using binary search, where we modify binary search to get an efficient solution.
A sorted and rotated array of size n is given, write a program to find minimum element in rotated sorted array. Rotation by k times means that the first k sorted elements of the array will move to the last k positions, and the last n - k sorted elements will move to the first n - k positions. Note: We don’t know how many times array is rotated in the given problem.
Binary search is an efficient algorithm to search a value in the sorted array using divide and conquer approach. It compares target value with value at mid-index and repeatedly reduces search interval by half. Searching continues until value is found or subarray size gets reduced to 0 (unsuccessful search). Time complexity of binary search is O(logn).
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.