资讯类响应式网站模板,网站设计手机型,建网站用什么服务器,淘宝客建网站要钱的吗寻找旋转排序数组中的最小值——I
题目链接 思路
首先我们以数组[1,2,3,4,5,6,7]举个例子#xff0c;经过旋转后它无非就这两种情况#xff1a;
情况一#xff1a;旋转过后数组变成两段有序数列#xff1a; 情况二#xff1a;旋转过后数组不变#xff0c;仍然有序经过旋转后它无非就这两种情况
情况一旋转过后数组变成两段有序数列 情况二旋转过后数组不变仍然有序 而这两种情况都有一个共性 以数组**最右边的值val**为研究对象最小值1右边的所有数必定小于val最小值左边的数必定大于val 我们可以画出如下的折线图来总结 知道了这些后我们就可以利用二分法求解了
我们设左边界为left右边界为right左右边界的中间值为mid由上面的分析可以知道若nums[mid] nums[right]就说明最小值一定在中间值的右侧中间值左侧的区域直接舍弃即可 若nums[mid] nums[right]就说明最小值一定在中间值的左侧或者就是中间值中间值右侧的区域直接舍弃即可 随着区间的不断缩小left和right最终就会相等其最后停留的位置也就是数组的最小值
实现代码
int findMin(int* nums, int numsSize) {int left 0;int right numsSize - 1;while (left right){int mid (right - left) / 2 left;//如果中间值大于最右边的值那么最小值一定在中间值的右边if (nums[mid] nums[right])left mid 1;//否则最小值就在最右边的值的左边也可能就是这个中间值elseright mid;}//循环结束时left和right所在的位置就是最小值的位置return nums[left];
}
