1、写在前面
手绘漫画系列正式上线!!!"图解LeetCode刷题计划" 来了!!!
今天是第十期,争取每天一期,最多两天一期,欢迎大家监督我。。。
最近依旧是二分查找算法呢~
使用新版的模板加上图解,相信你能更加理解二分法的使用!!!
2、题目
首先看一下题目,
分界条件就是左右两个数的大小,如果这个数大于左右两个数,那么它是峰值!
千万注意题中规定,不存在元素重复情况!!!
3、正文
首先分析一下情况,如果 mid
一直比右侧的数小,那么 mid
处的值肯定不是峰值。
确定一下 left
和 right
,然后编写二分查找模板。
可以看到,如果 nums[mid]>nums[mid 1]
,那么峰值一定在左侧,之所以没有等号,前面说过,题中强调没有重复数!
4、代码
int findPeakElement(int* nums, int numsSize){ int left=0; int right=numsSize-1; while(left<right){ int mid=left (right-left)/2; if(nums[mid]>nums[mid 1]){ right=mid; } else{ left=mid 1; } } return left;}