The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Find the minimum element in a sorted and rotated array.

Solution :-
We will use the principle of binary search [ Complexity :: O(log n) ].
See the implementation below.

#include<iostream>
using namespace std;

// find the minimum element in rotated and sorted array
int findMin(int arr[],int start,int end) {
   if(start == end) {
      return arr[start];
   }
   int mid = (start+end)/2;
   if(arr[start] > arr[mid]) {
      // min element lies in left subarray
      return findMin(arr,start,mid);
   }
   else
   if(arr[mid] > arr[end]) {
      // min element lies in right subarray
      return findMin(arr,mid+1,end);
   }
   else {
      // array is sorted but not rotated
      return arr[start];
   }
}

// main
int main() {
   int arr[] = { 3,4,5,6,7,1,2 };
   //int arr[] = { 7,11,15,16};
   int size = sizeof(arr)/sizeof(arr[0]);
   int min = findMin(arr,0,size-1);
   cout<<"\nMinimum element :: "<<min;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)