二分查找实战 蔚落 2021-07-25 02:38 316阅读 0赞 # 一 算法 # ## 1 首先确定该数组的中间的下标。 ## mid = (left + right) / 2 ## 2 然后让需要查找的数 findVal 和 arr\[mid\] 比较 ## 如果 findVal > arr\[mid\] , 说明要查找的数在 mid 的右边, 此时需要递归向右查找。 如果 findVal < arr\[mid\],说明要查找的数在 mid 的左边, 此时需要递归向左查找。 如果 findVal == arr\[mid\],说明找到,就返回。 ## 3 结束递归时机 ## a 找到就结束递归。 b 递归完整个数组,仍然没有找到 findVal ,也需要结束递归,此时 left > right, 退出。 # 二 实战一 # ## 1 要求 ## 对一个有序数组进行二分查找 \{1,8, 10, 89, 1000, 1234\} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。 ## 2 代码 ## import java.util.ArrayList; import java.util.List; /** * @className: BinarySearch * @description: 二分查找。注意:数组必须有序 * @date: 2021/3/13 * @author: cakin */ public class BinarySearch { /** * 功能描述:二分查找测试 * * @param args 命令行 * @author cakin * @date 2021/3/13 */ public static void main(String[] args) { // 待查找的数组 int arr[] = {1, 8, 10, 89, 1000, 1234}; // 二分法查找 int resIndex = binarySearch(arr, 0, arr.length - 1, 1000); System.out.println("resIndex=" + resIndex); } /** * 功能描述:二分查找算法 * * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findVal 要查找的值 * @return int 如果找到就返回下标,如果没有找到,就返回 -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; } } } ## 3 测试 ## resIndex=4 # 三 实战二 # ## 1 要求 ## 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到。例如:\{1,8, 10, 89, 1000, 1000,1234\},查找有序数组中的1000,并将下标存放到一个数组中。 ## 2 代码 ## import java.util.ArrayList; import java.util.List; /** * @className: BinarySearch * @description: 二分查找。注意:数组必须有序 * @date: 2021/3/13 * @author: cakin */ public class BinarySearch { /** * 功能描述:二分查找测试 * * @param args 命令行 * @author cakin * @date 2021/3/13 */ public static void main(String[] args) { // 待查找的数组 int arr[] = {1, 8, 10, 89, 1000, 1000, 1234}; List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000); System.out.println("resIndexList=" + resIndexList); } /** * 功能描述:二分法查找升级版,有多个相同的数值时,都能查找出来 * * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findVal 要查找的值 * @return List<Integer> 找到索引下标列表 * @author cakin * @date 2021/3/13 * @description: 1 当找到 mid 索引值,不要马上返回。 * 2 向 mid 索引值的左边扫描,将所有满足 1000 的元素的下标,加入到集合ArrayList * 3 向 mid 索引值的右边扫描,将所有满足 1000 的元素的下标,加入到集合ArrayList * 4 将Arraylist返回 */ public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) { // System.out.println("调用次数"); // 当 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 { List<Integer> resIndexlist = new ArrayList<>(); // 向 mid 索引值的左边扫描,将所有满足 1000 的元素的下标,加入到集合ArrayList int temp = mid - 1; while (true) { if (temp < 0 || arr[temp] != findVal) { // 退出 break; } // 将temp 放入到 resIndexlist resIndexlist.add(temp); temp -= 1; // temp左移 } resIndexlist.add(mid); // 向 id 索引值的右边扫描,将所有满足 1000 的元素的下标,加入到集合ArrayList temp = mid + 1; while (true) { if (temp > arr.length - 1 || arr[temp] != findVal) { // 退出 break; } // temp 放入到 resIndexlist resIndexlist.add(temp); temp += 1; // temp右移 } return resIndexlist; } } } ## 3 测试 ## resIndexList=[4, 5]
相关 二分查找 int binary_search(int num, int p, int len) { int high,low,mid; low = 0 川长思鸟来/ 2022年06月14日 09:16/ 0 赞/ 190 阅读
相关 二分查找 网上有看到说大多数程序员都不能写出二分查找的算法,所以呢,我不能成为那大多数程序员中的一个,果然瞎琢磨了半天,还是写出来了,mark下吧。 二分查找的数组得是从小到大升序排序 野性酷女/ 2022年06月04日 09:19/ 0 赞/ 199 阅读
相关 查找——二分查找 基本思想 二分查找是建立在有序顺序表基础上的!步骤如下: 1. 将表中间位置记录的关键字与给定K值进行比较,若两者相等,则查找成功。 2. 蔚落/ 2022年03月27日 03:46/ 0 赞/ 327 阅读
相关 二分查找 二分查找: 适用有序数组 public class BinarySearch { public static int[] arr = {1, 清疚/ 2022年03月09日 06:18/ 0 赞/ 235 阅读
相关 二分查找 1 二分查找 二分查找是一个基础的算法,也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较,如果被查找的键小于中间键,就在左子数组继续查找;如果 本是古典 何须时尚/ 2022年03月08日 10:28/ 0 赞/ 549 阅读
相关 二分查找 说在前面的话 略略略略略略啦略啦略啦略啦略略略啦啦啦啦略啦略略略———当你很认真的把这个读出声的时候,你会发现读完之后你会笑一下,然后笑骂了一下博主真傻bi,最后跟着也骂 谁借莪1个温暖的怀抱¢/ 2022年02月28日 14:24/ 0 赞/ 260 阅读
相关 二分查找 一下是一个正确的二分查找程序: int search(int array[], int n, int v) { int l 素颜马尾好姑娘i/ 2022年02月03日 14:11/ 0 赞/ 253 阅读
相关 二分查找 1.二分查找的定义 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。 折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 亦凉/ 2021年11月11日 12:44/ 0 赞/ 408 阅读
相关 二分查找实战 一 算法 1 首先确定该数组的中间的下标。 mid = (left + right) / 2 2 然后让需要查找的数 findVal 和 arr\[mid\] 蔚落/ 2021年07月25日 02:38/ 0 赞/ 317 阅读
还没有评论,来说两句吧...