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;

    int ans =-1;

    while(s<=e){

        if(arr[mid] == key){

            ans = mid;

            e = mid -1;            

        }

        else if(key> arr[mid]){   //right me jana hai

            s = mid +1;

        }

        else if(key < arr[mid]){   //left me jana hai

            e = mid -1;

        }

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

    }

    return ans;

}

int lastocc(vector<int>& arr, int n, int key){

    int s=0;

    int e=n-1, ans =-1;

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

    while(s<=e){

        if(arr[mid] == key){

            ans = mid;

            s = mid +1;            

        }

        else if(key> arr[mid]){   //right me jana hai

            s = mid +1;

        }

        else if(key < arr[mid]){   //left me jana hai

            e = mid -1;

        }

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

    }

    return ans;

}

pair<int, int> firstAndLastPosition(vector<int>& arr, int n, int k)

{

   pair<int, int> p;

    p.first = firstocc(arr, n, k);

    p.second = lastocc(arr, n, k);

    

    return p;

}



















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

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;     ...
Read more