- 相关推荐
C语言输出旋转后数组中的最小数元素的算法原理与实例
问题描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
思路：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是O(n)。但这个思路没有利用输入数组的特性。既然有时间复杂度更小的算法，我们容易想到二分查找，因为它的时间复杂度为O(logn)。这个问题是否可以运用二分查找呢？答案是肯定的。观察一下数组的特性，首先递增（称为递增a），然后突然下降到最小值，然后再递增（称为递增b）。当然还有一种特殊情况，就是数组递增，中间没有下降，即旋转元素个数为0。
对于一般的情况，假设A为输入数组，left 和 right 为数组左右边界的坐标，考察中间位置的值A[mid] ，如果A[mid] <= right="mid；如果A[mid]">= A[left]，表明处于递增a，因此调整左边界left = mid。当左右边界相邻时，较小的一个就是数组的最小值。其实，对于一般情况，右边界所指的元素为最小值。
【C语言输出旋转后数组中的最小数元素的算法原理与实例】相关文章：
C语言数组实例解析10-21
C语言数组元素的查询08-02
C语言中使用快速排序算法对元素排序的实例06-20
C语言冒泡排序算法实例06-15
对C语言数组的总结以及实例讲解09-01
C语言字符数组的几种输出方式05-21
C语言中实现KMP算法实例08-09
关于c语言约瑟夫问题输出序号算法10-16
C语言奇偶排序算法详解及实例代码10-30