java实现二分查找-两种方式,java二分法查找算法

　　00-1010二分搜索法递归实现概述递归实现代码循环实现代码(非递归)二分搜索法(递归，循环)

二分法查找

这里我用递归的方法来实现。

　　首先你需要确认搜索范围，也就是有左索引和右索引。每次取(左右)/2为中间值，将待搜索元素的大小与中间值进行比较。如果中间值较大，向前看，即递归范围为左，mid-1。反之，向右看，就是递归范围mid 1，右。如果相等，就找到了。

　　但是需要继续在这个索引的前后看，看有没有和它相等的值，添加到集合中，最后返回这个集合。

概述

包搜索；导入Java . util . ArrayList；导入Java . util . list；public class binary search { public static void main(String[]args){ int[]array={ 1，1，1，2，3，4，5，6，7 }；list integer integers=binary search(array，0，array.length - 1，1)；//for (Integer integer :整数){//system . out . print(Integer )；//} System.out.println(整数)；}公共静态列表整数二分搜索法(int [] array，int left，int right，int value){//如果左索引大于右索引，则表示已经完成了所有的遍历，没有找到对应的值。只需返回一个空集if(left right){ return new ArrayList integer()；}//获取中间值的下标(二分法)int mid=(左右)/2；//如果要找的值小于中间值，继续找If(value array[mid]){向左返回二分搜索法(array，left，mid-1，value)；//如果要找的值小于中间值，则向右查找} else If(value array[mid]){ return二分搜索法(array，mid 1，right，value)；//否则表示两者相等，已经找到}else {//了。还需要左右看看有没有相同的值listinteger结果list=new ArrayList()；//向左循环查找。如果有，就加到set int temp=mid-1；while(temp=0 array[temp]==value){ result list . add(temp)；temp-=1；}//向右循环查找。如果有，将其添加到集合中。temp=mid 1；while(temp array . length array[temp]=value){ result list . add(temp)；temp=1；}//将开头找到的索引页添加到集合中。result list . add(mid)；返回结果列表；

　　 } } //以下这段代码来自百度百科，供大家参考。 public static int binarySearch(Integer[] srcArray, int des) { //定义初始最小、最大索引 int start = 0; int end = srcArray.length - 1; //确保不会出现重复查找，越界 while (start <= end) { //计算出中间索引值 int middle = (end + start)>>>1 ;//防止溢出 if (des == srcArray[middle]) { return middle; //判断下限 } else if (des < srcArray[middle]) { end = middle - 1; //判断上限 } else { start = middle + 1; } } //若没有，则返回-1 return -1; }}

循环实现代码(非递归)

package search;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * @Author: sshdg * @Date: 2020/9/21 9:22 */public class BinarySearch2 { public static void main(String[] args) { int[] array = {1,1,1,1,1,2,3,4,5,6,7}; System.out.println(BinarySearch2.binarySearch(array, 7)); } public static List<Integer> binarySearch(int[] array, int key){ List<Integer> resultList = new ArrayList<>(); int start = 0; int end = array.length - 1; while (start <= end){ int mid = (start + end) / 2; int midValue = array[mid]; if (key > midValue){ //key比中间值大。向右找 start = mid + 1; } else if (key < midValue){ //key比中间值小。向左找 end = mid - 1; } else { //否则就找到了 //先向左找有没有相同值 int temp = mid -1; while (temp >= start && array[temp] == key){ resultList.add(temp); temp -= 1; } //将一开始找到的加入结果集 resultList.add(mid); //再向右找找有没有相同值 temp = mid + 1; while (temp <= end && array[temp] == key){ resultList.add(temp); temp += 1; } break; } } return resultList; }}

二分法查找（递归、循环）

public class BinarySearch { /** * @author JadeXu * @// TODO: 2020/12/7 二分查找 * 思路： * 1、获取数组的中间值，先获取下标，方便多次查找 * 奇数位的数组直接获取中间位，偶数位的数组获取中间的第一位或第二位都可，一般获取第一位（因为与奇数位获取中间值的方法一样） * 2、获取查找的区间范围，start：区间开始的下标，end：区间结束的下标 * 3、判断查找的数和中间位的数是否相同 * 相同时，直接返回需要的数据，跳出方法 * 大于时，即数可能在中间值右边的区间内，此时start = mid+1，即mid往后移一位，就得到了中间值右边区间的开始下标 * 小于时，即数可能在中间值左边的区间内，此时end = mid-1，即mid往前移一位，就得到了中间值左边区间的结束下标 * 当一个区间里，开始下标小于等于结束下标时，该区间才是有效区间，才能继续查找。否则无效，返回找不到，跳出方法 */ //循环 /** * @param arr 已经升序好的int[] * @param num 需要查找的数字 * @return 找到则返回下标，没找到则返回-1 */ private static int binarySearchByCycle(int[] arr,int num) { int start = 0; int end = arr.length - 1; while (start <= end){ int mid = (start + end) / 2; if(num == arr[mid]){ return mid; }else if(num > arr[mid]){ start = mid + 1; }else { end = mid - 1; } } return -1; } //递归 /** * @param arr 已经升序好的int[] * @param num 需要查找的数字 * @param start 区间开始下标 * @param end 区间结束下标 * @return 找到则返回下标，没找到则返回-1 */ private static int binarySearchByRecursion(int[] arr,int num,int start,int end) { int mid = (start + end) / 2; if(num == arr[mid]){ return mid; }else if(num > arr[mid]){ start = mid + 1; }else { end = mid - 1; } if(start <= end){ mid = binarySearchByRecursion(arr,num,start,end); //递归继续寻找 }else { mid = -1; } return mid; }}

以上为个人经验，希望能给大家一个参考，也希望大家多多支持盛行IT。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

java实现二分查找-两种方式,java二分法查找算法

目录

二分法查找

概述

循环实现代码(非递归)

二分法查找（递归、循环）

相关文章阅读