算法前提:
==>> 必须采用顺序存储结构
==>> 必须按关键字大小有序排列
算法思路是:
1.每次去数组中的中间值与被查找的值进行比较
2.如果中间值小于被查找的值,则选择中间值右边的数组,重复1,直到发现与被查找的值相等的数组元素或返回某个值,表示被查找的值在数组中不存在。
3.如果中间值大于被查找的值,则选择中间值左边的数组,重复1,直到发现与被查找的值相等的数组元素或返回某个值,表示被查找的值在数组中不存在。
下面是我个人的代码实现:
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