• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find min element in Sorted Rotated Array (Without Duplicates)

August 4, 2014 by Dhaval Dave

Problem: Find the minimum element in a sorted and rotated array if duplicates not allowed:
Example: {3, 4, 5, 6, 7, 1, 2} output: 1

Algorithm:
This problem can be easily solved in O(n) time complexity buy traversing the
whole array and check for minimum element.
Here we are using a different solution which takes O(Log n)
Let us look at this approach, we are using a modified version of Binary Search Tree algorithm.

Thanks Dheeraj for  sharing Question and Code  for this .

Code:

#include<iostream> 
 using namespace std;

int BST(int A[],int low,int high){
  int mid=low+(high-low)/2;
  if ( mid == high ) return A[mid];  //if size of sub array is 1
  if(mid < high && mid > low && A[mid] < A[mid + 1] && A[mid -1] > A[mid] ) 
  return A[mid];  
//compare value of mid + 1,mid, mid-1 if they exist 

 if(A[mid] > A[high]) {
 if(A[mid + 1] < A[mid]) return A[mid + 1];
 else return BST(A, mid + 1, high); //check in right sub array
 }
 else
 {
 if(A[mid] < A[mid – 1]) return A[mid];
 else return BST(A , low , mid – 1); //check in left sub array
 } 
}

int main()
{
 int A[]={3,4,5,6,7,1,2};
 int n= sizeof(A)/sizeof(A[0]);
 cout<<BST(A,0,n-1)<<endl;
}

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Array, Binary Search

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Binary Tree Isomorphic to each other

FizzBuzz Solution C C++

How Radix sort works

Minimum insertions to form a palindrome

Wrong Directions given find minimum moves so that he can reach to the destination

Trapping Rain Water

How strtok() Works

Apriori algorithm C Code Data Mining

Daughter’s Age VeryGood Puzzle

Advanced SQL Injection

Handle duplicates in Binary Search Tree

25 horses 5 tracks Find 3 fastest puzzle

Maximum size of square sub matrix with all 1’s in a binary matrix

Edit Distance ( Dynamic Programming )

Printing each word reverse in string

Reliance Jio Software Developer Interview Experience

Urban Ladder Written Test.

Implement LRU Cache

Sort Stack in place

Knight Tour Problem (Graph – Breadth First Search)

Stock Buy Sell to Maximize Profit

Count Possible Decodings of a given Digit Sequence

Password Predictor

Facebook Interview Question : Interleave List

HackeEarth Flipkart’s Drone

Find min element in Sorted Rotated Array (With Duplicates)

Find position of the only set bit

Mirror of Tree

Find if a binary tree is height balanced ?

Client Server C program

Copyright © 2025 · Genesis Framework · WordPress · Log in