二分查找：
这个算法是比较简单的，容易理解的。这个算法是对有序的数组进行查找，所以想要使用这个算法那么
首先先要对数组进行排序。
其实有三个指针，开始指针，末尾指针，中间指针，来开始。折半查找。
步骤如下：
1、确定三个指针，start,end,middleIndex。
2、判断start<=end,如果满足，就执行这个方法，不满足，就返回，找不到。
3、在2的前提下，我们对其折半查找，middleIndex = start+end >> 1，取中间值。
4、判断中间位置的值和目标值是否相等，如果相等就返回这个位置。
不相等，如果中间位置的值比目标值大，就在左半边的数组来递归查找这个目标值，
否则在右边的数组查找递归这个目标值。
5.返回值。
|
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
package
com.test4;
/**
* 二分查找
*
* @author sdc
*
*/
public
class
BinarySearch {
// 查找某个元素需要的次数
static
int
count;
public
static
void
main(String[] args) {
}
/**
* 二分查找--递归的形式，二分查找是对有序的数组查找
*
* @param sortArray
* @param start
* @param end
* @param target
* @return
*/
public
static
int
binarySearch(
int
[] sortArray,
int
start,
int
end,
int
target) {
if
(sortArray ==
null
) {
return
-
1
;
}
int
sortArrayLength = sortArray.length;
if
(sortArrayLength ==
1
) {
return
sortArray[
0
];
}
count++;
// 真正开始了，查找
if
(start <= end) {
// 中间的位置
int
middleIndex = (start + end) >>
1
;
// 中间的值
int
middleData = sortArray[middleIndex];
if
(middleData == target) {
return
middleIndex;
}
else
if
(middleData < target) {
return
binarySearch(sortArray, middleIndex +
1
, end, target);
}
else
{
return
binarySearch(sortArray, start, middleIndex -
1
, target);
}
}
else
{
// 给的返回值不对
return
-
1
;
}
}
/**
* 二分查找-非递归的形式
*
* @param sortArray
* @param target
* @return
*/
public
static
int
serarch(
int
[] sortArray,
int
target) {
if
(sortArray ==
null
) {
return
-
1
;
}
// 起始位置
int
start =
0
;
// 结束位置
int
end = sortArray.length -
1
;
while
(start <= end) {
// 一直循环查找
// 中间位置
int
middleIndex = (start + end) >>
1
;
if
(sortArray[middleIndex] == target) {
return
middleIndex;
}
else
if
(sortArray[middleIndex] > target) {
end = middleIndex -
1
;
}
else
{
start = middleIndex +
1
;
}
}
return
-
1
;
}
}
|
结束：
本文转自 豆芽菜橙 51CTO博客，原文链接:http://blog.51cto.com/shangdc/1918333
