二分法查找，顾名思义就是要将数据每次都分成两份然后再去找到你想要的数据，我们可以这样去想，二分法查找很类似与我们平时玩的猜价格游戏，当你报出一个价格时裁判会告诉你价格相对于真实值的高低，倘若是低了那我们一定会再说出一个略高的价格，反之亦然。在二分法查找时要求传入的数据必须已经有序，假设现在为升序，然后每次将所寻找的值与中间值(数组左边界+(右边界-左边界)/2)作比较，大了则去寻找中间值左侧数据，小则寻找中间值右侧数据。
二分法查找比较局限性的就是只能操作一个已经排序了的数组。
方法一
下面为一个二分法实现的完整代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
package dichotomy; import java.util.arrays; import java.util.scanner; import static java.lang.system.out; public class erchange {
private static scanner in; public int find( int a[], int b) //a为所要查找的数 { int mid,low= 0 ,high; high=a.length- 1 ; while (low<=high) { mid=low+(high-low)/ 2 ; if (b<a[mid]) { high=mid- 1 ; } else if (b>a[mid]) { low=mid+ 1 ; } else { return mid+ 1 ; } } return 0 ; } public static void main(string[] args) { int a[]; int t; int sum= 0 ; erchange p= new erchange(); int q2 = 0 ; in = new scanner(system.in); out.println( "请输入数组长度" ); q2= in.nextint(); a= new int [q2]; out.println( "请输入数组元素" ); for ( int i= 0 ;i<a.length;i++) { a[i]=in.nextint(); } out.println( "排序后数组为" ); arrays.sort(a); for ( int i = 0 ; i < a.length; i++) { out.print(a[i]+ " " ); } out.println(); out.println( "请输入所要查找的数若未查找到该数则输出-1" ); q2=in.nextint(); for ( int i= 0 ;i<a.length;i++) { if (q2==a[i]) { t= 1 ; } else { t= 0 ; } sum=sum+t; } if (sum== 0 ) { out.println( "-1" ); } else { out.println( "所输入的数在第" +p.find(a,q2)+ "位" ); } } |
方法二
代码实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
public class binarysearch { //进行二分法查找的前提是数组已经有序！ public static int rank( int key, int nums[]) { //查找范围的上下界 int low= 0 ; int high=nums.length- 1 ; //未查找到的返回值 int notfind=- 1 ; while (low<=high) { //二分中点=数组左边界+(右边界-左边界)/2 //整数类型默认取下整 int mid=low+(high-low)/ 2 ; //中间值是如果大于key if (nums[mid]>key) { //证明key在[low,mid-1]这个区间 //因为num[mid]已经判断过了所以下界要减一 high=mid- 1 ; } else if (nums[mid]<key) { //证明key在[mid+1,high]这个区间 //同样判断过mid对应的值要从mid+1往后判断 low=mid+ 1 ; } else { //查找成功 return mid; } } //未成功 return notfind; } public static void main(string[] args) { system.out.println( "请输入数据数量：" ); scanner scanner= new scanner(system.in); int amount=scanner.nextint(); int num; int nums[]= new int [amount]; int i= 0 ; while (i<amount) { nums[i]=scanner.nextint(); i++; } arrays.sort(nums); system.out.println( "请输入想要查找的值" ); int key=scanner.nextint(); int answer=rank(key,nums); if (answer!=- 1 ) { system.out.println( "所查找的数据存在：" +nums[answer]); } else { system.out.println( "您所查找的数据不存在" ); } }
} |
方法三、算法代码实现之二分法查找
封装成类：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
package com.roc.algorithms.search;
/** * 二分法查找 * * @author roc */ public class binarysearch {
/** * @param a 升序排列的数组 * @param k 待查找的整数 * @return 如果查到有就返回对应角标，没有就返回-1 */ public static int search( int [] a, int k) { int lo = 0 , hi = a.length - 1 ; while (lo <= hi) { int m = (lo + hi) >> 1 ; if (a[m] < k) { lo = m + 1 ; } else if (a[m] > k) { hi = m - 1 ; } else { return m; } } return - 1 ; } } |
测试：
|
1 2 |
int [] a = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; system.out.println(binarysearch.search(a, 6 )); |
输出：
6
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
原文链接：https://blog.csdn.net/qq_40833779/article/details/80095715