JAVA实现二分查找

  • Z时代
  • 2024-01-10
  • 分类：综合

java

二分查找又称折半查找、二叉查找，它是一种效率较高的查找方法。

前提

给定一已排好序的n个元素a[0 : n-1]，现要在这n个元素中找出一特定元素x。

算法 思想

首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大 于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

 1 public class BinarySearch {
 2 
 3     /***
 4      * 
 5      * @param a 已排好序的数组
 6      * @param dst 需要查找的目标值
 7      * @return 查找到目标值返回目标值在数组中的位置，没有超重到目标值返回-1
 8      */
 9     public int binarySearch(int[] a, int dst) {
10         
11         int flag = 0;
12         //先判断数组是顺序还是倒序
13         if (a[0] > a[a.length - 1]) {
14             System.out.println("array is reverse order");
15             flag = 1;  //数组为倒序
16         }
17         
18         int mid = -1;
19         int low = 0;
20         int high = a.length - 1;
21         if (0 == flag) {
22             while (low <= high) {
23                 mid = low + (high-low)/2; //此处不用(low + high)/2是防止low + high值溢出
24                 if (a[mid] == dst) {
25                     printSearchResult(a,dst,mid);
26                     return mid;
27                 } else if (dst < a[mid]) {
28                     high = mid - 1;
29                 } else {
30                     low = mid + 1;
31                 }
32             }
33         } else {
34             while (low <= high) {
35                 mid = low + (high-low)/2; //此处不用(low + high)/2是防止low + high值溢出
36                 if (a[mid] == dst) {
37                     printSearchResult(a,dst,mid);
38                     return mid;
39                 } else if (dst < a[mid]) {
40                     low = mid + 1;
41                 } else {
42                     high = mid - 1;
43                 }
44             }
45         }
46         
47         
48         System.out.println("not find the num " + dst + " in the array");
49         return -1;
50         
51     }
52     
53     /***
54      * 打印查找结果
55      * @param a 数组
56      * @param dst 查找的目标值
57      * @param position 目标值在数组中的位置
58      */
59     private void printSearchResult(int[] a,int dst, int position) {
60         String tmp = "find the num " + dst + " in the array {";
61         for (int i = 0; i < a.length - 2; i++) {
62             tmp += a[i] + ",";
63         }
64         tmp += a[a.length - 1] + "}, position is " + position;
65         System.out.println(tmp);
66     }
67     
68     public static void main(String[] args) {
69         int a[] = {1,3,5,7,8,9,10,12,15,17};
70         BinarySearch binarySearch = new BinarySearch();
71         binarySearch.binarySearch(a,17);
72         binarySearch.binarySearch(a, 8);
73         int b[] = {17,13,11,9,7,6,4,2,1};
74         binarySearch.binarySearch(b,17);
75         binarySearch.binarySearch(b, 4);
76         binarySearch.binarySearch(b, 1);
77     }
78     
79 }

 1 public class BinarySearch {
 2     public static void main(String[] args) {
 3         int[] arys = {1, 3, 6, 11, 35, 36, 45, 66, 75};
 4         System.out.println(binarySearch(arys, 6, 0, arys.length - 1));
 5     }
 6 
 7     private static int binarySearch(int[] arys, int element, int begin, int end) {
 8         // TODO Auto-generated method stub
 9         if (begin <= end) {
10             int mid = (begin + end) >> 1;
11             if (arys[mid] == element)
12                 return mid;
13             else if(arys[mid] > element) {
14                 return binarySearch(arys, element, 0, mid - 1);
15             } else {
16                 return binarySearch(arys, element, mid + 1, end);
17             }
18         } else
19         return -1;
20     }
21 }

以上是 JAVA实现二分查找 的全部内容， 来源链接： utcz.com/z/393999.html

回到顶部