宜宾网站网站建设,chinacd wordpress第三性,网站重新备案需要多长时间,域名价格查询二分查找也称 半查找#xff08;Binary Search#xff09;#xff0c;它时一种效率较高的查找方法。但是#xff0c;折半查找要求线性表必须采用顺序存储结构#xff0c;而且表中元素按关键字 有序 排列。 注意#xff1a;使用二分查找的前提是 该数组是有序的。 在实际开… 二分查找也称 半查找Binary Search它时一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字 有序 排列。 注意使用二分查找的前提是 该数组是有序的。 在实际开发中如果对应的索引不存在我们一般都是返回一个负数而且经常用 - 1 来表示。 请对一个有序数组进行二分查找 { 18108910001234}输入一个数看看该数组是否存在此数并且求出下标如果没有就提示 “没有这个数” 。 课后思考题{181089100010001234} 当一个有序数组中有多个相同的数组时如何将所有的数值都查找到比如这里面的1000。 { 18108910001234 } 二分查找的思路分析 1、首先确定该数组的中间的下标 mid left right / 2 2、然后让需要查找的数 findVal 和 arr[mid] 比较 2.1、findVal arr[mid] 说明你要查找的数在 mid 的右边因此需要 递归 的向右查找 2.1、findVal arr[mid] 说明你要查找的数在 mid 的左边因此需要 递归 的向左查找 2.3、findVal arr[mid]说明找到就返回 //什么时候我们需要结束递归。 1找到就结束递归 2递归完整个数组仍然没有找到findVal也需要结束递归 当left right 就需要退出 请对一个有序数组进行二分查找 { 18108910001234}输入一个数看看该数组是否存在此数并且求出下标如果没有就提示 “没有 这个数” 。 public class BinarySearch {public static void main(String[] args) {int arr[] {1, 8, 10, 89, 1000, 1234};int resIndex binarySearch(arr, 0, arr.length - 1, 88);System.out.println(resIndex);}/*** param arr 数组* param left 左边的索引* param right 右边的索引* param findVal 要查找的值* return 如果找到就返回下标如果没有找到就返回-1*/public static int binarySearch(int[] arr, int left, int right, int findVal) {//当left right 时说明递归整个数组但是没有找到if (left right) {return -1;}int mid (left right) / 2;int midVal arr[mid];if (findVal midVal) { //向右递归return binarySearch(arr, mid 1, right, findVal);} else if (findVal midVal) { //向左递归return binarySearch(arr, left, mid - 1, findVal);} else {return mid;}}
} 完成一个课后思考题{1810100010001234}当一个有序数组中有多个相同的数值时如何将所有的数值都查找到比如这里的1000 思路分析 1、在找到 mid 索引值不要马上返回 2、向mid索引值的左边扫描将所有满足1000的元素的下标加入到集合ArrayList 3、向mid索引值的右边扫描将所有满足1000的元素的下标加入到集合ArrayList 4、将ArrayList返回 public class BinarySearch1 {public static void main(String[] args) {int arr[] {1, 8, 10, 89, 1000, 1000, 1000, 1000,1234};ListInteger resIndexList binarySearch2(arr, 0, arr.length - 1, 1000);System.out.println(resIndexList);}/*** param arr 数组* param left 左边的索引* param right 右边的索引* param findVal 要查找的值* return 如果找到就返回下标如果没有找到就返回-1*/public static ArrayListInteger binarySearch2(int[] arr, int left, int right, int findVal) {//当left right 时说明递归整个数组但是没有找到if (left right) {return new ArrayListInteger();}int mid (left right) / 2;int midVal arr[mid];if (findVal midVal) { //向右递归return binarySearch2(arr, mid 1, right, findVal);} else if (findVal midVal) { //向左递归return binarySearch2(arr, left, mid - 1, findVal);} else {ArrayListInteger resIndexlist new ArrayListInteger();//向mid索引值的左边扫描将所有满足1000的元素的下标加入到集合ArrayListint temp mid - 1;while (true) {if (temp 0 || arr[temp] ! findVal) { //退出break;}//否则就temp放入到resIndexlistresIndexlist.add(temp);temp - 1; //temp 左移}resIndexlist.add(mid);//向mid索引值的右边扫描将所有满足1000的元素的下标加入到集合ArrayListtemp mid 1;while (true) {if (temp arr.length || arr[temp] ! findVal) { //退出break;}//否则就temp放入到resIndexlistresIndexlist.add(temp);temp 1; //temp右移}return resIndexlist;}}
} public class BinarySearch2 {public static void main(String[] args) {int[] array new int[]{10, 11, 12, 13, 14, 15, 16, 17};int target 10;int index search(array, target);System.out.println(index);}public static int search(int[] array, int target) {int min 0;int max array.length - 1;while (min max) {int mid (min max) / 2;if (array[mid] target) {return mid;}if (array[mid] target) {min mid 1;}if (array[mid] target) {max mid - 1;}}return -1;}
} public class BinarySearch3 {public static void main(String[] args) {int[] arr2 new int[]{-98, -34, 2, 34, 54, 66, 79, 105, 210, 333};int dest1 35;int head 0; //初始的首索引int end arr2.length - 1; //初始的末索引boolean isFlag1 true;while (head end) {int middle (head end) / 2;if (dest1 arr2[middle]) {System.out.println(找到了指定的元素位置为 middle);isFlag1 false;break;} else if (arr2[middle] dest1) {end middle - 1;} else {head middle 1;}}if (isFlag1) {System.out.println(很遗憾没有找到的啦);}}
}public class BinarySearch4 {public static void main(String[] args) {int[] arr2 new int[]{2, 4, 5, 8, 12, 15, 19, 26, 37, 49, 51, 66, 89, 100};int target 17;int head 0; //默认的首索引int end arr2.length - 1; //默认的尾索引boolean isFlag false;while (head end) {int middle (head end) / 2;if (target arr2[middle]) {System.out.println(找到了 target ,对应的位置为 middle);isFlag true;break;} else if (target arr2[middle]) {head middle 1;} else {end middle - 1;}}if (!isFlag) {System.out.println(不好意思未找到);}}
} public class BinarySearch5 {public static void main(String[] args) {int[] arr {7, 23, 79, 81, 103, 127, 131, 147};System.out.println(binarySearch(arr, 150));}public static int binarySearch(int[] arr, int number) {int min 0;int max arr.length - 1;while (true) {if (min max) {return -1;}int mid (min max) / 2;if (arr[mid] number) {max mid - 1;} else if (arr[mid] number) {min mid 1;} else {return mid;}}}
}
