本文共 3409 字,大约阅读时间需要 11 分钟。
首先确定该数组的中间的下标
mid = (left + right) / 2
然后让需要查找的数 findVal 和 arr[mid] 比较
1 findVal > arr[mid] 说明要查找的数在mid的右边,因此需要递归的向右查找
2 findVal < arr[mid] 说明要查找的数在mid的左边,因此需要递归的向左查找
3 findVal == arr[mid] 说明找到,返回下标值
// 什么时候需要结束递归?
/** * 二分查找算法[使用二分查找的前提是该数组是有序的] */public class BinarySearch { public static void main(String[] args) { int[] arr = { 1,8,10,89,1000,1234}; int arrIndex = binarySearch(arr, 0, arr.length - 1, 1000); System.out.println("所要查找的值的数组下标为:" + arrIndex); } /** * 二分查找[使用二分查找的前提是该数组是有序的] * @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, left, mid - 1, findVal); } else if (findVal > midVal) { // 向右递归 return binarySearch(arr, mid + 1, right, findVal); } else { // 找到 return mid; } }}
所要查找的值的数组下标为:4
课后思考题: {1, 8, 10, 89, 1000, 1000, 1000, 1234} 当一个有序数组中, 有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000
public static void main(String[] args) { int[] arr2 = { 1, 8, 1000, 89, 1000, 1000, 1000, 1234}; Listlist = binarySearch2(arr2, 0, arr2.length - 1, 1000); System.out.println("所要查找的值的数组下标为:" + list.toString());}/*** 课后思考题: {1, 8, 1000, 89, 1000, 1000, 1000, 1234}* 当一个有序数组中, 有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000** @param arr 有序数组* @param left 左索引* @param right 右索引* @param findVal 要查找的值* @return 如果找到就返回集合,否则返回一个空的集合*/public static List binarySearch2(int[] arr, int left, int right, int findVal) { // 当 left > right 时,说明递归整个数组,但是没有找到 if (left > right) { return new ArrayList (); } 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 { // 思路分析 // 1. 在找到 mid 索引值,不要马上返回 // 2. 向 mid 索引值的左边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList // 3. 向 mid 索引值的右边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList // 4. 将 Arraylist返回 List resIndexList = new ArrayList (); // 向 mid 索引值的左边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList int temp = mid - 1; for (int i = 0; i <= temp; i++){ if (findVal == arr[i]) { resIndexList.add(i); } } resIndexList.add(mid); // // 向 mid 索引值的右边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList temp = mid + 1; for (int i = temp; i < arr.length - 1; i++) { if (findVal == arr[i]) { resIndexList.add(i); } } return resIndexList; }}
所要查找的值的数组下标为:[4, 5, 6]
转载地址:http://ekiwi.baihongyu.com/