。。。剑指Offer之——旋转数组的最小数字。。。
1 public int minNumberInRotateArray(int[] array) { 2 // 1、如果输入的数组为空，则返回0（返回0是题目要求的） 3 // 2、如果输入的数组的内容为空，则返回0（返回0是题目要求的） 4 if (array == null || array.length == 0) { 5 return 0; 6 } 7 // index1指向数组的开头 8 int index1 = 0; 9 // index2指向数组的的结尾 10 int index2 = array.length - 1; 11 int mid;//指向index1～index2的中间 12 while (array[index1] >= array[index2]) { 13 mid = (index1 + index2) / 2; 14 // 如果index1，index2，mid三者指向的数值相等的话，则顺序查找 15 if (array[index1] == array[index2] && 16 array[index1] == array[mid]) { 17 return orderSearch(array); 18 } 19 // 1、如果中间的值大于等于index1指向的值，说明，最小值在后面 20 // 2、将index1指向中间，缩小查找范围 21 if (array[mid] >= array[index1]) { 22 index1 = mid; 23 } 24 // 1、如果中间的值小于等于index2指向的值，说明，最小值在前面 25 // 2、将index2指向中间，缩小查找范围 26 if (array[mid] <= array[index2]) { 27 index2 = mid; 28 } 29 // 如果两个指针指向相邻的位置，则最小值是index2指向的值 30 if (index2 - index1 == 1) { 31 return array[index2]; 32 } 33 } 34 // 如果while条件不满足，说明序列本身就是已经排好序的（从小到大），则第一个是最小的 35 return array[index1]; 36 } 37 // 顺序查找最小值 38 public int orderSearch(int[] array) { 39 int result = array[0];//姑且认为第一个是最小的 40 for (int i = 0; i < array.length; i++) { 41 // 如果后面发现有比result还要小的，则将result替换 42 if (array[i] < result) { 43 result = array[i]; 44 } 45 } 46 // 返回最小值 47 return result; 48 }
更多精彩
