二分查找思想寻找有序数组中查找最小值

左手的ㄟ右手 2022-08-12 01:15 160阅读 0赞

思想：循环有序数组最大的特点是利用二分查找时，有一边总是有序的，利用这个特点，利用value存储历史最小值

当左边有序，则用A\[low\]与value比较即可得出当前左边的最小值，然后跳转到右边看是否存在更小的；

如果右边有序，则用A\[mid\]与value比较，得出右边的最小值，然后跳转到左边查看是否有更小的。

算法复杂度为O（logn）

代码如下:

#include<iostream>
    #include<stdio.h>
    #include<assert.h>
    using namespace std;
    int Binary_Search(int *A,int size)
    {
    	assert(A != NULL);
    	int low = 0;
    	int value = A[0];//初始化
    	int high = size - 1;
    	while(low <= high)
    	{
    		int mid = (low + high) / 2;
    		if(A[low] <= A[mid])//左有序,注意‘=’的使用
    		{
    			if(A[low] < value)//与左边有序的最小值比较
    			{
    				value = A[low];
    				low = mid + 1;//跳转至右边试图寻找最小值
    			}
    			else 
    				low = mid + 1;
    		}
    		else//右有序
    		{
    			if(A[mid] < value)//与右边有序的最小值比较
    			{
    				value = A[mid];
    				high = mid - 1;//跳转至左边试图寻找最小值
    				
    			}
    			else
    				high = mid - 1;
    		}
    	}
    	return value;
    }
    int main()
    {
    	int A[10] = {4,5,6,7,8,9,0,1,2,3};
    	cout<<Binary_Search(A,10);
    	return 0;
    }