197-找出旋转数组中的最小值

逃离我推掉我的手 2022-10-30 10:20 199阅读 0赞

**题目如下：**  
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3,4,5,1,2\] 为 \[1,2,3,4,5\] 的一个旋转，该数组的最小值为1。

示例 1：  
输入：\[3,4,5,1,2\]  
输出：1

示例 2：  
输入：\[2,2,2,0,1\]  
输出：0 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 **NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。**

**解题思路如下：**  
中心思想其实就是使用二分查找的方法，逐步的逼近这个最小值，首先这个旋转数组将一个非递减的数组分成了两个子数组，前一个数组的值都比后一个数组的值大，并且两个子数组都是非递减的数组，而且我们可以知道这个最小值肯定是在前一个数组和后一个数组的交界处。也就是后一个数组的第一个值。

## 采用二分法解决问题 ##

**mid = left + （right -left）/2;**  
首先说下不要使用（left +right）/2；这种方式去求数组的中间位置，可能会造成溢出。  
**需要考虑3种情况：**  
**1、arr\[mid\] > arr\[right\];**  
出现这种情况arr类似\[3, 4, 5, 0, 1, 2\],此时最小数字移动在mid的右边。执行left = mid + 1；  
**2、array\[mid\] == array\[right\];**  
出现这种情况array类似\[0, 1, 1, 1, 1,\]或者\[1, 1, 1, 0, 1\],此时最小数字不好判断在mid左边还是右边，这个时候只好一个个的去试  
执行right = right - 1;  
**3、array\[mid\] < array\[right\]:**  
出现这种情况的arr类似\[2,2,3,4,5,6,6\],此时最小数字一定就是arr\[mid\]或者在mid的左边。因为右边必然都是递增的。执行 right = mid；  
**注意：**  
如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字  
比如 arr= \[4,6\]  
arr\[left\] = 4 ;arr\[mid\] = 4 ; arr\[right\] = 6 ;  
如果right = mid - 1，就会产生错误， 因此我们执行right = mid；  
但情形(1)中left = mid + 1就不会产生错误。

**代码如下：**

#include<stdio.h>
    
    int minNumberInRotateArray(int *arr,int len)
    {
        
    	if (len == 0)
    	{
        
    		return 0;
    	}
    	int left = 0, right = len - 1;
    	while (left < right)
    	{
        
    		int mid = (right - left) / 2 + left;
    		if (arr[mid] > arr[right])
    		{
        
    			left = mid + 1;
    		}
    		else if (arr[mid] < arr[right])
    		{
        
    			right = mid;
    		}
    		else
    		{
        
    			right = right - 1;
    		}
    	}
    	return arr[left];
    }
    
    int main()
    {
        
    	int arr[]={
        3,4,5,1,2};
    	int len=sizeof(arr)/sizeof(arr[0]);
    	printf("%d\n",minNumberInRotateArray(arr,len));
    
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/40784157e37846fc9d333df5546c5df4.png