Java编程内功-数据结构与算法「二分查找」

需求

对于一个有序的编程数组进行二分查找{1,8,10,89,1000,1234}，输入一个数看看该数组是内功否存在此数，并求出下标，数据算法如果没有就提示”没有这个数据”。结构

思路分析

首先确定该数组中间的分查下标 mid=(left+right)/2. 然后让需要查找的数findValue和arr[mid]比较，findValue > arr[mid]，编程说明要查找的内功数在arr[mid]的右边，因此向右递归.findValue < arr[mid]，数据算法说明要查找的源码库结构数在arr[mid]的左边，因此向左递归.findValue == arr[mid]，分查说明找打，编程就返回。内功 退出递归的数据算法条件找到就结束递归。递归完整个数组仍然没有找到findValue，结构需要结束递归，分查即当 left > right

代码案例

package com.xie.search; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class BinarySearch {     static int count = 0;     public static void main(String[] args) {         int[] arr = new int[102];         arr[0] = 1;         arr[1] = 1;         for (int i = 2; i < 102; i++) {             arr[i] = i;         }         List<Integer> indexList = binarySearch(arr, 0, arr.length - 1, 1);         System.out.println("indexList = " + indexList);         System.out.println("查找次数：" + count);         /*         indexList = [1, 0]         查找次数：6          */     }     /**      * 二分查找,查找符合值得所有索引集合      *      * @param arr       数组      * @param left      左边索引      * @param right     右边索引      * @param findValue 查找的值      * @return 找到就返回所有索引的集合，没有就返回空      */     public static List<Integer> binarySearch(int[] arr, int left, int right, int findValue) {         count++;         List<Integer> indexList = new ArrayList<Integer>();         //当left > right时，说明递归完毕         if (left > right) {             return new ArrayList<Integer>();         }         int mid = (left + right) / 2;         int midVal = arr[mid];         if (findValue > midVal) {             //查找的高防服务器值比中间值大，向右递归             return binarySearch(arr, mid + 1, right, findValue);         } else if (findValue < midVal) {             //查找的值比中间值小，向左递归             return binarySearch(arr, left, mid - 1, findValue);         } else {             //如果找到了，再向左扫描，将满足条件的加入indexList             int temp = mid - 1;             while (true) {                 if (temp < 0 || arr[temp] != findValue) {                     break;                 }                 indexList.add(temp);                 temp--;             }             //再向右扫描,将满足条件的加入indexList             temp = mid + 1;             while (true) {                 if (temp > right || arr[temp] != findValue) {                     break;                 }                 indexList.add(temp);                 temp++;             }             indexList.add(mid);             return indexList;         }     } } 

 【编辑推荐】

惊呆，一条SQL，Oracle炸了... 我用Python制作微信动态表情符 7款提升工作效率的工具，太适合新手小白了吧 微软 Edge 90 正式版发布：新增下载管理菜单，字体渲染更清晰 阿里云盘 PC 版抢先体验：不限速但仍有遗憾