【题目】
把一个数组最开始的若干个元素搬到数组的末尾, 我们称之数组的旋转。
输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素。
例如数组{ 3, 4, 5, 1, 2} 为{ l, 2, 3, 4, 5}的一个旋转,该数组的最小值为 1。
/**
*
* 暴力遍历寻找
*
*二分查找方法:
*1.两个指针指向数组第一个和最后一个元素(第一个元素应该大于等于最后一个元素)
*2.找数组中间的元素,如果中间元素大于等于第一个指针指向的元素,则中间元素位于前面的递增序列,那么最小值应该位于中间元素后面,移动left
*3.如果中间元素小于等于第二个指针指向的元素,则中间元素位于后面的递增序列,那么最小值应该位于中间元素的前面,移动right
*4.如此不断循环,最终两个指针会指向两个相邻的元素,此时第二个指针指向的就是最小元素,这就是循环结束的条件。
*
*为了解决特例:如果将排序数组的前面0个元素搬到最后面,即数组本身,我们初始化mid为left,
*一旦发现数组中第一个元素小于最后一个元素,直接返回一个元素;
*对于{1,0,1,1,1}这样的数组,无法正确查找,也就是左中右三个指针的元素都相同时,只能顺序遍历查找。
*/
public class 旋转数组的最小数字 { public static int xzsz1(int[] arr) { for(int i = 1;iarr[i] && arr[i] < arr[i+1]) { return arr[i]; } } if(arr[arr.length-1]= arr[right]) { if(right - left == 1) { mid = right; break; } mid = (left + right)/2; if(arr[left] == arr[right] && arr[left] == arr[mid]) { return bl(arr,left,right); } if(arr[mid] >= arr[left]) { left = mid; }else if(arr[mid] <= arr[right]) { right = mid; } } return arr[mid]; } private static int bl(int[] arr, int left, int right) { int res = arr[left]; for(int i = left+1;iarr[i]) { res = arr[i]; } } return res; } public static void main(String[] args) { int[] arr = {2,3, 4, 5, 1}; int[] arr2 = {1,1,1,0,1}; int[] arr3 = {1,0,1,1,1}; int[] arr4 = {1,2,3, 4, 5}; System.out.println(xzsz1(arr)); System.out.println(xzsz2(arr2)); System.out.println(xzsz2(arr3)); } }