旋转数组中的最小值 8

基于二分法

? ?

index1为首，index2为尾，indexMid指向中间

? ?

当Number[index1]大于等于Number[index2]的条件满足时

? ?

判断index2和index1的差距是否等于1

? ?

如果相等，说明index2即为那个突变点，最小值，将index2赋给indexMid，最终返回Number[indexMid]

? ?

如果不等，就取indexMid=index1和index2的中间值

? ?

如果index1，index2和indexMid相等的话，那么就需要在index1和index2之间用顺序查找

? ?

如果不等，若index1指向的数小于indexMid指向的数，将index1更新为indexMid

? ?

若indexMId指向的数小于index2指向的数，将index2更新为indexMid

? ?

顺序查找

? ?

相邻两个数比较，如果前一个数大于后一个数，那么后一个数就是最小值。如果不是，则往后找

? ?

package minNumberInRotatedArray8;

? ?

public class OriCode_MinInRotatedNumber {

public static void main(String[] args) {

//????????????????int[] numbers = { 3, 4, 5, 1, 2 };

//????????????????int[] numbers = { 1, 0, 1, 1, 1 };

int[] numbers={1,1,1,0,1};

int result = Min(numbers);

? ?

System.out.println(result);

? ?

}

? ?

static int Min(int[] numbers) {

int index1 = 0;

int index2 = numbers.length - 1;

int indexMid = index1;

while (numbers[index1] >= numbers[index2]) {

if (index2 - index1 == 1) {

indexMid = index2;

break;

}

indexMid = (index1 + index2) / 2;

if (numbers[index1] == numbers[index2]

&& numbers[index1] == numbers[indexMid]) {

return MinInOrder(numbers, index1, index2);

}

if (numbers[indexMid] >= numbers[index1]) {

index1 = indexMid;

} else if (numbers[indexMid] <= numbers[index2]) {

index2 = indexMid;

}

? ?

}

return numbers[indexMid];

? ?

};

? ?

static int MinInOrder(int[] numbers, int index1, int index2) {

int result = numbers[index1];

for (int i = index1 + 1; i < index2; i++) {

if (result > numbers[i]) {

result = numbers[i];

}

}

return result;

? ?

}

}