友点企业网站,网站建设和程序开发哪个好,有没有永久免费的服务器,晚上必看正能量网站短视频最小元素的位置以旋转次数为索引的位置#xff0c;但是没有告诉旋转次数#xff0c;换一种思路
当遇到arr[index] arr[index1]时#xff0c;index1为最小元素的位置。首位位置独立比较。但是这种方法还是遍历数组 观察两组数的中间值与首尾的值#xff0c;又由于数组…
最小元素的位置以旋转次数为索引的位置但是没有告诉旋转次数换一种思路
当遇到arr[index] arr[index1]时index1为最小元素的位置。首位位置独立比较。但是这种方法还是遍历数组 观察两组数的中间值与首尾的值又由于数组是分段升序的我们可以列出以下情况
arr[left] arr[index] arr[right]此时说明最小值为left
arr[left] arr[index] arr[right]此时说明最小值在index~right
arr[left] arr[index] arr[right]此时说明最小值在left~index
arr[left] arr[index] arr[right]这种情况不可能 arr[left] arr[index]说明最小值在左侧arr[index] arr[right]说明最小值在右侧 代码
import org.junit.Test;public class LookForMin {Testpublic void test() {int[] arr new int[]{7, 8, 9, 11, 21, 23, 45, 0, 1, 2};//10int[] arr1 new int[]{15, 2, 3, 5, 6, 8, 9, 11};//8int[] arr2 new int[]{1, 3, 5};int[] arr3 new int[]{2, 2, 2, 0, 1};int[] arr4 new int[]{3, 3, 3, 1, 2};int[] arr5 new int[]{3,3,1,3};int[] arr6 new int[]{1,1};System.out.println(lookForMin(arr));System.out.println(lookForMin(arr1));System.out.println(lookForMin(arr2));System.out.println(lookForMin(arr3));System.out.println(lookForMin(arr4));System.out.println(lookForMin(arr6));}public static int lookForMin(int[] arr) {int left 0, right arr.length - 1;if (arr[right] arr[left]) {return arr[left];} else {while (left right) {int index left (right - left) / 2;while(arr[index] arr[right] right 0){//right0避免越界right--;}if (arr[left] arr[index] arr[index] arr[right]) {//等于是为了防止最终结束时left仍然保持不变导致结果错误left index 1;} else {right index;}}}return arr[right];}
}
