宜昌网站制作,网站开发vsc网站开发公司,无印良品官方网络商城,如何上传ftp网站程序1.初次相识 二分查找又称折半查找#xff0c;是一种在有序数组中查找特定元素的算法。二分查找的基本思想是#xff1a;通过不断地二分数组的中间元素#xff0c;缩小查找区间#xff0c;直到找到目标元素或者确定目标元素不存在为止。 二分查找的时间复杂度为O(logn)…1.初次相识 二分查找又称折半查找是一种在有序数组中查找特定元素的算法。二分查找的基本思想是通过不断地二分数组的中间元素缩小查找区间直到找到目标元素或者确定目标元素不存在为止。 二分查找的时间复杂度为O(logn)比线性查找的时间复杂度O(n)要小很多但是二分查找的前提是必须在有序数组中进行。 2.思想分析 1.确定该数组的中间下标 middle(leftright)/22.需要查找的数index和array【middle】比较2.1 index array【middle】说明要查找的数在middle的右边递归向右查找2.2 index array【middle】说明要查找的数在 middle的左边递归向左查找2.3 index array【middle】说明找到返回什么时候递归结束1.找到就结束2.递归完整个数组未找到也许结束条件: lift rigtht 3.代码实现 public static int binarySearch(int[] arr, int left, int right, int index) {//直接结束递归if (left right) {return -1;}int middle (left right) / 2;int middleVal arr[middle];if (index middleVal) {return binarySearch(arr, middle 1, right, index);} else if (index middleVal) {return binarySearch(arr, left, middle - 1, index);} else {return middle;}}
发现一个问题如果有重复数字也只能返回第一数字的下标 4.代码优化 思路: 1.再找到middle时不要立马返回2.向middle索引的左边扫描将满足条件元素的下标加入到ArrayList集合3.向middle索引的右边扫描将满足条件元素的下标加入到ArrayList集合4.将ArrayList返回 public static ArrayListInteger binarySearch(int[] arr, int left, int right, int index) {//直接结束递归if (left right) {return new ArrayListInteger();}int middle (left right) / 2;int middleVal arr[middle];if (index middleVal) {return binarySearch(arr, middle 1, right, index);} else if (index middleVal) {return binarySearch(arr, left, middle - 1, index);} else {ArrayListInteger list new ArrayList();int temp middle - 1;//向左边查找的第一个元素while (true) {if (temp 0 || arr[temp] ! middleVal) {//退出条件break;}list.add(temp);//找到放进集合temp--;//temp左移}list.add(middle);//中间的放进去temp middle 1;while (true) {if (temp arr.length - 1 || arr[temp] ! middleVal) {break;}list.add(temp);temp;}return list;}}
5.测试一把 public static void main(String[] args) {int[] array new int[]{1, 2, 3, 4, 5, 6, 6};Scanner scanner new Scanner(System.in);System.out.println(请输入你要查找的数字:);int num scanner.nextInt();ArrayListInteger lists binarySearch(array, 0, array.length - 1, num);System.out.println(你查找的数字: num ,下标: lists);}
