【前言】

今天是力扣打卡第7天！

好快呀，一周已经过去了，铁汁们，你们坚持下来了没？

 原题：寻找峰值

题目描述：

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

【敲黑板】：本题属于查找类题型，又看到时间复杂度是O(logN)，所以不难想到二分查找

示例1：

  

   

    

     

    
    

     

      输入：nums = [1,2,3,1]
     
    
   

    

     

    
    

     

      输出：2
     
    
   

    

     

    
    

     

      解释：3 是峰值元素，你的函数应该返回其索引 2。
     
    
  
 

示例2：

  

   

    

     

    
    

     

      输入：nums = [1,2,1,3,5,6,4]
     
    
   

    

     

    
    

     

      输出：1 或 5 
     
    
   

    

     

    
    

     

      解释：你的函数可以返回索引 1，其峰值元素为 2；
     
    
   

    

     

    
    

     

           或者返回索引 5， 其峰值元素为 6。
     
    
  
 

注意： 

使用二分法是有要求的，前提是一定要有序！ 那么这道题目该怎么去解呢？我们也不能去把它先排个序，因为会把索引弄乱，那该咋办呢？请朝后看...

 找到了一个规律：

nums[mid] > nums[mid + 1] 时，mid前边一定存在峰值；

nums[mid] < nums[mid + 1] 时，mid+1后边一定存在峰值

代码执行

  

   

    

     

    
    

     

      int findPeakElement(int* nums, int numsSize){
     
    
   

    

     

    
    

     
    //考虑特殊情况
     
    
   

    

     

    
    

     
    if(nums == NULL || numsSize == 0){
     
    
   

    

     

    
    

     
        return -1;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    int left = 0;
     
    
   

    

     

    
    

     
    int right = numsSize - 1;
     
    
   

    

     

    
    

     
    int mid = 0;
     
    
   

    

     

    
    

     
    while(left <= right){
     
    
   

    

     

    
    

     
        //如果while循环中的表达式中没有判断==时的情况，这条语句也就可以省略了
     
    
   

    

     

    
    

     
        //之所以加上，是为了套用二分的那个结构，等到后面熟悉使用了就不会这样啦
     
    
   

    

     

    
    

     
        if(left == right){
     
    
   

    

     

    
    

     
            return left;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              mid = left + (right - left) / 2;
     
    
   

    

     

    
    

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

    

     

    
    

     
            //mid+1后边一定存在峰值
     
    
   

    

     

    
    

     

                  left = mid + 1;
     
    
   

    

     

    
    

     

              }else{
     
    
   

    

     

    
    

     

                  right = mid;
     
    
   

    

     

    
    

     
            //mid前边一定存在峰值
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return left;
     
    
   

    

     

    
    

     

      }
     
    
  
 

复杂度分析

时间复杂度：O(logN)

空间复杂度：O(1)

结语

今天是力扣打卡第7天！

感谢力扣里面的大佬，向你们学习[致敬]！！

886，咱们明儿再见！！！

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121170784