DAY 2
leetcode-153 搜索旋转排序数组
Tag:二分查找——原理比较容易想明白
题目详述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例1:
输入: [3,4,5,1,2]
输出: 1
示例2 :
输入: [4,5,6,7,0,1,2]
输出: 0
为什么不直接用min,哈哈哈简单又快捷
Java版本(公众号提供)
主要思路(公众号给出)
- 如果这个旋转数组只有一个数直接返回这个数;
- 如果这个旋转数组的第一个数小于数组的最后一个数,那么说明旋转数组本身就是升序的,也就是说没有进行旋转,直接返回第一数;
- 而对于其他情况,采取二分查找的思想进行查找,当在二分的过程中,找到这样的一个数(这个数既比它的左边的数下,又比它右边的数小),那么就是最小的数直接返回即可;
- 如果在循环结束以后没有找到,说明肯定是在边界,因为最小值如果在中间,那么必然已经经过了判断直接返回了结果,所以这个时候只需要比较数组的第一个数和最后一个数。
对于旋转数组如何理解:原数组按照升序顺序排列,以中间的一个值为中心,将数组翻转。
##上述代码转换为Python类型