Category Archives: Binary Search

Search in Rotated Sorted Array

By | | , , , ,
Leave a comment

Write a code to search in rotated sorted array.

Given a sorted array and a target value.  Suppose this sorted array is rotated any number of times.

Write a code to search a target value in a sorted and rotated array. Return the index of a target value. If the target value is not found then return -1.

NOTE: The array only contains distinct values.

For example:

Input: {4, 5, 6, 7, -1, 0, 1, 2},  target = 0

Output: 5

In the above example, we have to search 0 in the rotated array. The element 0 is present at 5th index.

→

Find Peak Element in Array

By | | , , ,
Leave a comment

Given an array of integers, write a code to find peak element in array. The array may contain multiple peak elements, in that case, return anyone peak element.

Peak Element

Peak element is an element which greater than it’s neighbours. For strictly decreasing array, the first element is the peak element. And for strictly increasing array the last element is the peak element.

For example:

Example 1:

Input: {2, 3, 4, 7, 5} , Output: 7

The element 7 is greater than it’s neighbours (4 and 5).

Example 2:

Input: {8, 7, 6, 5, 4}, Output: 8

In this example, An array is strictly decreasing, so the first element is the peak element.

Example 3:

Input: {2, 3, 4, 5, 6}, Output: 6

An array is strictly increasing, so the last element is the peak element.

Example 4:

Input: {2, 2, 2, 2, 2}, Output: 2

All the array element is the same, So every element in this array is the peak element.

→

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.

→