旋转数组-二分法变种

感谢链接：https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba?answerType=1&f=discussion
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

针对的目标待处理数组是下面这样的：

下图中上面的曲线可以看做原数组，从竖线处切分后，得到下面的图。我们的目标就是找那个最低点。

/**

* 第一种做法，通过题意可以了解到，只需要输出旋转后数组最小元素就行了，所以直接给数组进行排序。

a. 可以使用Java内置的排序方法，数组的第一个元素就是最小元素，最后输出即可，Arrays.sort()的排序时间复杂度是根据数组长度来判断,这个内置排序的基本类型是quick sort快速排序，对象类型是优化过后 merge sort合并排序，时间复杂度是O(nlgn) 空间复杂度O(1)

b.也可以使用二分排序等自己写的排序方法

publicintminNumberInRotateArray(int[] array) {

if(array.length ==0|| array ==null)return 0;

Arrays.sort(array);

return array[0];

}

感谢链接：https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba?answerType=1&f=discussion
来源：牛客网

3 4 5 1 2 （一般情况）
1 2 3 4 5 / 2 2 2 2 2（容易想到的点）
1 0 1 1 1 / 1 1 1 0 1（特例）

直接进行顺序的查找,复杂度为O(n).

但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).
这里我们需要利用带有条件的二分法来进行求解:

第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = (start + end) // 2.

第二步我们能够看到,当我们选取的中间值 mid 所对应的值大于 start 所对应的值时,说明此时 mid 还在第一有序的数组中,而我们所要求解的最小值是在第二个有序数组的第一个位置,此时也就是在 mid 的后面,我们就将 start 移到 mid 所在的后一个元素的位置.

第三步,当我们的 end 所对应的值大于 mid 所对应的值时,说明最小值可能是 mid 所对应的值或者在 mid 的前面,我们将 end 移到 mid 所在的位置.

第四步,最后我们的 end 所在的位置就是最小值的位置,直接返回即可.

有这样的特例比如数组 10111 , 这是会出现当 start mid end 所对应位置的值相等,这时候我们的程序就不能找到最小值,当出现这样的情况是我们采用将 start 和 end 区间里面的值进行顺序查找来找出最小值.

--------------------

链接：https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba?answerType=1&f=discussion
来源：牛客网

二分查找变种，没有具体的值用来比较。那么用中间值和高低位进行比较，看处于递增还是递减序列，进行操作缩小范围。

处于递增：low上移
处于递减：high下移（如果是high-1，则可能会错过最小值，因为找的就是最小值）
其余情况：low++缩小范围
特殊情况：

代码：

public int minNumberInRotateArray(int [] array) {
//Arrays.sort(array);
//数组为空的情况
if(array.length ==0|| array ==null)
return 0;
//数组中只有一个元素
if(array.length ==1)
return array[0];
//数组包含两个及其以上元素的情况，使用二分查找算法实现
//利用好非递减排序的数组这个性质,显然，这是一个局部排好序的列表
//循环终止条件：区间长度为1：包括low=high或者arr.low<arr.high
int low =0;
int high = array.length -1;
int mid =0;
while(low < high){
// 子数组是非递减的数组，10111
if(array[low] < array[high])
return array[low];
mid = low + (high - low) /2;
if(array[mid] > array[low])
low = mid +1;
else if(array[mid] < array[high])
high = mid;
else low++;
}
return array[low];

}

#二分法旋转数组##笔试题目#