binary-search

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 (the new merged array will be an array of length 2n). 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.

Binary search is an efficient algorithm for searching a value in a sorted array using the divide and conquer idea. It compares the target value with the value at the mid-index and repeatedly reduces the search interval by half. The search continues until the value is found or the subarray size gets reduced to 0. The time complexity of the binary search is O(log n).

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, the program should find the first and last occurrence of a given element. The goal is to design an algorithm with O(log n) time complexity. Note that this is an excellent question to learn problem-solving using binary search. Here, the binary search needs to be applied 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.

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.