Peak Index in a Mountain Array || Binary Search practice example || Leet Code poblem #852

-

 || Peak Index in a Mountain Array
 || Binary Search practice example
 || Leet Code poblem #852


Given an integer array arr we have to return the index of peak element. 

 Array first increase and then decrease.

 Format  a[1] < a[2] <  a[3] <........a[n].......> a[2]  > a[1]

 We have to return the index of a[n]


  Input: arr = [0,1,0]
  Output: 1
Input: arr = [0,2,1,0]
Output: 1
Input: arr = [0,10,5,2]
Output: 1
***************CODE****************
//TIME COMPLEXITY IS O(LOG N)

 int peakIndexInMountainArray(vector<int>& arr) {

        int s=0;

        int e=arr.size()-1;

        int mid= s + (e-s)/2;

        while (s<e){

            

            if(arr[mid] < arr[mid+1]){

                s = mid +1;

            }

            else

                e= mid;

            

            mid= s + (e-s)/2;

        }

        return s;

    } 

Comments

Post a Comment

Popular posts from this blog

Allocate Book Problem Solution || Code Studio

-
Image
ALLOCATE BOOK PROBLEM SOLUTION PROBLEM STATEMENT:- Recommendation: First you have to try then go for solution. For practice  Click here  . Given an array ‘arr’ of integer numbers . where ‘arr[i]’ represents the number of pages in the ‘i-th’ book. There are ‘m’ number of students and the task is to allocate all the books to their students. Allocate books in such a way that: 1. Each student gets at least one book. 2. Each book should be allocated to a student. 3. Book allocation should be in a contiguous manner. You have to allocate the book to ‘m’ students such that the maximum number of pages assigned to a student is minimum. Example: Let’s consider ‘n=4’ (number of books ) and ‘m=2’ (number of students). ‘arr = { 10, 20, 30, 40 }’. All possible way to allocate the ‘4’ books in ‘2’ number of students is - 10 | 20, 30, 40 - sum of all the pages of books which allocated to student-1 is ‘10’, and student-2 is ‘20+ 30+ 40 = 90’ so maximum is ‘max(10, 90)= 90’. 10, 20 | 30, 40 - su...
Read more

First and Last position of an element in sorted array | Binary Search Practice Example | Code Studio Interview Question

-
 Here I am writting only function solution not main part... ||It is based on Binary Search Example Problem is there is given an array and you have to find a particular key of first and last index of that arry. Example:- Input format 2     // number of test Cases 6  3        // size of array      &&   the key element which have to find there first and last index in array 0  5  5  6  6  6 8  2 0  0  1  1  2  2  2  2   Output -1   -1     ///output is -1 because 3 is not present in the array 4    7    /// output is 4(first occurance) and 7 ( the last Occurance) ***************************************CODE************************************** int firstocc(vector<int>& arr, int n, int key){     int s=0;     int e=n-1;     int mid = s+(e-s)/2;     in...
Read more