旋转数组的最小数字
理论在考查二分查找的办法
知识点
一个不蕴含反复元素的升序数组在通过旋转之后，能够失去上面可视化的折线图：
- 通过旋转，最小值右侧的数肯定严格小于最小值左侧的数
- 数组最初一个数为x，则在数组最小值右侧的数肯定严格小于x，在数组最小值左侧的数肯定严格大于x，前提是不包含反复元素，因而利用这个寻找数组最右侧的值，来用二分法解题
- 定义左边界为left，右边界为right区间的中点为pivot，最小值必定就在区间内，利用区间的中点值和右侧边界值进行比拟，
- 比右边界值小则阐明区间的中点值在最小值的右侧，因而咱们能够疏忽二分查找区间的右半局部
- 比右边界值大则阐明区间的中点值在最小值的左侧，因而咱们能够疏忽二分查找区间的左半局部
因为数组不蕴含反复元素，并且只有以后的区间长度不为 11，\it pivotpivot 就不会与 \it highhigh 重合；而如果以后的区间长度为 11，这阐明咱们曾经能够完结二分查找了。因而不会存在 nums[pivot]=nums[right] 的状况。
题解
本题是没有反复元素的所以没有思考元素雷同的时候
return left和right都能够
元素反复的数组
本题外面有反复元素，所以得思考left和right的值雷同的时候
-
当两头节点和右边界点的值雷同的时候，无奈判断最小值在两头节点的左侧还是右侧，也就无奈判断扭转左边界值还是右边界值，因而不能轻易疏忽某一段元素，咱们只能确定无论右边界点的值是不是最小值，数组中都有一个和他雷同的两头节点值，因而就能够疏忽右边界点的值，而后对右边界点往左侧挪动一个索引，也就是right–，如果还是和两头节点值一样就持续right–，反复直到右边界点right节点的值和两头节点的值不雷同
题解
return left和right都能够
然而下面这样right–相当于把雷同的元素全副遍历了一遍，如果反复元素很多，那就须要遍历很多遍，耗资源对下面算法进行改良
找到两个相等之后就间接在外面遍历，不出循环了剑指题目解答
发表回复