Find the Peak Element | C++ Placement Course | Lecture 29.5

Показать описание

Notes of this Lecture:

Рекомендации по теме

Комментарии

Int searchPeak(vector<int> nums){
int n = nums.size() ;
int s = 0 ;
int e = n - 1 ;
while(s < e){
int m = s + (e-s) / 2 ;
if(nums[m] > nums[m+1]){
e = m ;
}
else{
s = m + 1 ;
}
}
return s ;
}

Using Binary Search
Time Complexity = O(LogN)
Space complexity = O(1)

HyperGaming-qctd

okay see the condition
1. if arr[mid] <arr[mid-1] then we will go left side, ik now u will be thinking like what if my array is like this-[ 7, 8, 9, 6, 5, 4, 3, 6]
okay so look mid is 3 and arr[3]=6.and arr[3-1]=9 now the condition is getting true so we will go left, and for this 9 will be the peak element. but what if the array is like this [9, 8, 7, 6, 5, 4, 3, 6] look nowhere 9 is at edge 0+1 index have greater value so still we got peak element, and if we don't have decreasing or increasing trend then means for sure we will get at least one peak element.
so basically the problem is to find a peak element, not all peak elements.

tarunbisht

This explanation was really helpful.
Thanks a lot

md.ualiurrahmanrahat

Will there be no need of base case?
like when (low>high)return -1?

PrinceSingh-nxbx

1:36 second line Descending array:first element is peak is true not last element

amansrivastava

my doubt is that the binary search can only be applied on a sorted array but in this case we are using binary search on an unsorted array so there is a good chance that we are missing out on a peek element so if we use binary search on this problem does that mean the array have multiple peeks. Please correct me if I am wrong.

msyugandhar

but the concept isn't cleared yet... what about 9 which is also greater then 8... i m not getting the whole point of peak element...

edit: i searched about this problem on the internet and found, we just have to return any one of the peak elements...

mjustboring

If we give arr[ ]={1, 2, 5, 4, 5, 6, 8, 9, 10}
It not work bcoz in first mid we go for right part to find it but our peak is in left part

moizbohra

Sabse easy case kyuu liya gya h for dry run🤦🏻‍♀️🤦🏻‍♀️

arushigarg

The solution is not right. Binary Search can only be used to process on the list of sorted numbers. Here, the input is unsorted, thus it is quite possible that after first calculation of mid, even if we move to left, the answer might be on the right side. I don't really get the thought process here. We cannot blindly use Binary Search just because they say O(log n).

prajwalshenoy

isn't that the same Q as that of Lecture 8.4 problem 4 -- RECORD BREAKING DAY

its_neel_ok

it is given that given array is not sorrted
let take a array
1 2 7 5 10 18 19 20 22
here mid value is 10
if we compare 10 with 5 and 18
acc to algo we should go towards right but on left there is a peak element ( 2, 7, 5)
what about that?
pls explain

harshagarwal

Why we used binary search?
To give answer in O (log N) time.

rutvikrana

This course was said to be completed in Jan 2021 .. April is going on and aap placement phase tak bhi complete nhi kara paaye
Competitive coding phase ki kya baat kare....
Take your words seriously @amanDhattarwal

alankrita._