算法入门-二分查找算法

==>>  必须采用顺序存储结构 
==>>  必须按关键字大小有序排列

 1 /**
 2  * 
 3  */
 4 package com.b510.algorithms;
 5 
 6 /**
 7  * 二分查找算法是在已经排序好的数组中查找出某个值
 8  * @author hongten(hongtenzone@foxmail.com)<br>
 9  * @date 2013-6-7
10  */
11 public class PartTwoDichotomy {
12 
13     public static void main(String[] args) {
14         int[] a = { 1, 3, 4, 5, 6, 8, 9, 13, 14, 17, 21 };
15         int x = 21;
16         int index = dichotomy(a, x);
17         String result = index == -1 ? "被查询的值[" + x + "]不在数组中！" : "被查询的值[" + x + "]在数组中,且下标为：" + index;
18         System.out.println(result);
19     }
20 
21     /**
22      * 二分法查询算法
23      * 
24      * @param a
25      *            已经排序好的数组
26      * @param x
27      *            需要查找的值
28      * @return -1表示x不在数组a中，否则返回数组a的n下标，其中<code>a[n] == x</code>
29      */
30     public static int dichotomy(int[] a, int x) {
31         if (a == null) {
32             throw new NullPointerException("数组不能为空!");
33         } else {
34             int index = 0;
35             int last = a.length - 1;
36             int middle = 0;
37             while (index >= 0 && index <= last) {
38                 print(a, index, last + 1);
39                 middle = (index + last) / 2;
40                 if (a[middle] == x) {
41                     return middle;
42                 }
43 
44                 if (a[middle] < x) {
45                     index = middle + 1;
46                 }
47 
48                 if (a[middle] > x) {
49                     last = middle - 1;
50                 }
51             }
52             return -1;
53         }
54     }
55 
56     /**
57      * 打印数组信息
58      * 
59      * @param a
60      * @param index
61      *            从数组的index地方开始
62      * @param last
63      *            到数组last地方结束
64      */
65     public static void print(int[] a, int index, int last) {
66         if (a != null && index >= 0 && index <= last) {
67             StringBuffer buffer = new StringBuffer();
68             for (int i = index; i < last; i++) {
69                 buffer.append(a[i] + "   ");
70             }
71             System.out.println("需要继续进行查找的数组为：" + buffer);
72         }
73     }
74 }

需要继续进行查找的数组为：1   3   4   5   6   8   9   13   14   17   21   
需要继续进行查找的数组为：9   13   14   17   21   
需要继续进行查找的数组为：17   21   
需要继续进行查找的数组为：21   
被查询的值[21]在数组中,且下标为：10

需要继续进行查找的数组为：1   3   4   5   6   8   9   13   14   17   21   
需要继续进行查找的数组为：9   13   14   17   21   
需要继续进行查找的数组为：17   21   
需要继续进行查找的数组为：21   
被查询的值[212]不在数组中！

需要继续进行查找的数组为：1   3   4   5   6   8   9   13   14   17   21   
需要继续进行查找的数组为：9   13   14   17   21   
需要继续进行查找的数组为：9   13   
需要继续进行查找的数组为：13   
被查询的值[13]在数组中,且下标为：7

需要继续进行查找的数组为：1   3   4   5   6   8   9   13   14   17   21   
需要继续进行查找的数组为：1   3   4   5   6   
需要继续进行查找的数组为：1   3   
被查询的值[1]在数组中,且下标为：0

需要继续进行查找的数组为：1   3   4   5   6   8   9   13   14   17   21   
被查询的值[8]在数组中,且下标为：5