java实现二分法的完整代码

时间:2022-11-16 11:58:11

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