算法入门-二分查找算法
添加时间:2013-6-7 点击量:
算法前提：
==>> 必须采取次序存储布局
==>> 必须按关键字大小有序分列
算法思路是：
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
我俩之间有着强烈的吸引力。短短几个小时后，我俩已经明白：我们的心是一个整体的两半，我俩的心灵是孪生兄妹，是知己。她让我感到更有活力，更完美，更幸福。即使她不在我身边，我依然还是感到幸福，因为她总是以这样或者那样的方式出现在我心头。——恩里克·巴里奥斯《爱的文明》
算法前提：
==>> 必须采取次序存储布局
==>> 必须按关键字大小有序分列
算法思路是：
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
我俩之间有着强烈的吸引力。短短几个小时后，我俩已经明白：我们的心是一个整体的两半，我俩的心灵是孪生兄妹，是知己。她让我感到更有活力，更完美，更幸福。即使她不在我身边，我依然还是感到幸福，因为她总是以这样或者那样的方式出现在我心头。——恩里克·巴里奥斯《爱的文明》
