【面试题】剑指offer08--旋转找出最小的数字

谁借莪１个温暖的怀抱￠ 2022-06-14 07:49 155阅读 0赞

对于一个数组，里面肯定存在一个最小的数，找出这个最小的数字，有很多的方法

将数组里面的数字旋转一次，即可找到那个最小的数字

这将要使用二分查找的方法：

以下是代码的实现：

#define _CRT_SECURE_NO_DEPRECATE
    #include<tchar.h>
    #include<iostream>
    using namespace std;
    
    int BinarySearchMinNum(int* arr, int length)
    {
    	if (arr != NULL && length > 0)
    	{
    		int low = 0;
    		int high = length - 1;
    		int mid = low;
    
    		while (arr[low] >= arr[high])
    		{
    			if (high - low == 1)
    			{
    				mid = high;
    				break;
    			}
    
    			mid = low + ((high - low) >> 1);
    			if (arr[low] == arr[high] && arr[low] == arr[mid])
    			{
    				int min = arr[low];
    				for (int i = low + 1; i <= high; i++)
    				{
    					if (min > arr[i])
    					{
    						min = arr[i];
    					}
    				}
    				return min;
    			}
    			if (arr[mid] >= arr[low])
    			{
    				low = mid;
    			}
    			else if (arr[mid] <= arr[high])
    			{
    				high = mid;
    			}
    		}
    		return arr[mid];
    	}
    	else
    	{
    		cout << "数组为空！" << endl;
    		return -1;
    	}
    }
    
    int main()
    {
    	int arr1[5] = { 3, 4, 5, 1, 2 };
    	cout << BinarySearchMinNum(arr1, 5) << endl;
    	int arr2[5] = { 2, 4, 2, 2, 2 };
    	cout << BinarySearchMinNum(arr2, 5) << endl;
    	int arr3[5] = { 0 };
    	cout << BinarySearchMinNum(arr3, 5) << endl;
    	int arr4[5] = { 4, 4, 1, 1, 2 };
    	cout << BinarySearchMinNum(arr4, 5) << endl;
    	system("pause");
    	return 0;
    }

运行的结果如下：

![Center][]

[Center]: /images/20220614/5e72480a274b48928bb50c3c4f71f4da.png