binary-search

9 articles

Cover illustration for Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

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.

Cover illustration for Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

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.

Cover illustration for Search in a row wise and column wise sorted matrix

Search in a row wise and column wise sorted matrix

You have given row-wise and column-wise sorted 2D matrix and integer k, write a program to search k in the 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.

Cover illustration for Median of two sorted arrays of same size

Median of two sorted arrays of same size

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.

Cover illustration for Row With Max 1s

Row With Max 1s

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.

Cover illustration for Binary Search Algorithm

Binary Search Algorithm

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).