个人中心
gpt4 book ai didi

java实现二分法的完整代码

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java实现二分法的完整代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

二分法查找，顾名思义就是要将数据每次都分成两份然后再去找到你想要的数据，我们可以这样去想，二分法查找很类似与我们平时玩的猜价格游戏，当你报出一个价格时裁判会告诉你价格相对于真实值的高低，倘若是低了那我们一定会再说出一个略高的价格，反之亦然。在二分法查找时要求传入的数据必须已经有序，假设现在为升序，然后每次将所寻找的值与中间值(数组左边界+(右边界-左边界)/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( "您所查找的数据不存在" );
         }
     }
 
}

方法3、算法代码实现之二分法查找 。

封装成类:

?
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 。

最后此篇关于java实现二分法的完整代码的文章就讲到这里了,如果你想了解更多关于java实现二分法的完整代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： Win10连接打印机提示0x00004005错误代码怎么办？
文章推荐： 使用qt quick-ListView仿微信好友列表和聊天列表的示例代码
文章推荐： HTTP协议各版本的区别的你知道吗？
文章推荐： Java调用用户芝麻信用分
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com