Tag Archives: Binary Search

Find Minimum in Rotated Sorted Array

By | | , ,
Leave a comment

In this tutorial, I am going to discuss a very interesting problem find minimum in rotated sorted array.

Given an array which is sorted in ascending order is rotated at some unknown point. Write a code to find the minimum element in a sorted and rotated array.

You may assume no duplicate exists in the array.

For example:

Example 1:

Input: [6, 7, 8, 1, 2]
Output: 1

The minimum element in this sorted and rotated array is 1.

Example 2:

Input: [8, 9, 10, 1, 0, 1, 2]
Output: 0

In this example, the minimum element is 0.

→

Single Element in a Sorted Array

By | | , , ,
Leave a comment

Single Element in a Sorted Array. Find the element that appears once in a sorted array where every other element appears twice.

Given a sorted array of integers. In this array, every element appears twice except one element which appears only once. Write a code to find the element which appears only once.

For example:

Example 1:

Input: [1, 1, 2, 2, 3, 4, 4, 7, 7]

Output: 3

Except 3 every other element appears twice.

Example 2:

Input: [1, 1, 2, 2, 3, 3, 4, 5, 5]
Output: 4

NOTE – Try to solve this problem in O(logn) time complexity and by using constant space O(1).

→