二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，二分查找要求线性表必须采用 顺序存储结构，而且表中元素按关键字有序排列。
基本思路
首先，假设表中元素是按升序排列，将表中间位置的数的值与待查找数的值比较，如果两者相等，则查找成功； 否则利用中间位置记录将表分成前、后两个子表， 若中间位置值 < 待查找值，则进一步查找前一子表， 若中间位置值 > 待查找值，则进一步查找后一子表。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
分析
用递归法来写代码
首先确定该数组的中间下标 mid = ( left+right ) / 2
然后让带查找的数的值 findVal 和 arr[mid] 比较 findVal < arr[mid]； 说明要查找的数再mid的右边，因此向右继续查找。 findVal > arr[mid]； 说明要查找的数再mid的左边，因此向右继续查找。 findVal == arr[mid]； 说明找到，就返回。
什么时候结束递归？
找到就结束 。 即：findVal == arr[mid] 时递归完整个数组，仍没有找到 findVal ，也需要结束递归。即：left > right 时
代码
public class BinarySearch {
public static void main(String
[] args
) {
int[] arr
={1,2,3,40,41,42,100};
int index
= BinarySearch(arr
, 0, arr
.length
- 1, 2);
System
.out
.println("index:" + index
);
}
public static int BinarySearch(int[] arr
, int left
, int right
, int findVal
) {
System
.out
.println("Binary run~~~");
if (left
> right
) {
return -1;
}
int mid
=(left
+right
)/2;
int midVal
= arr
[mid
];
if (findVal
< midVal
) {
return BinarySearch(arr
, left
, mid
- 1, findVal
);
} else if (findVal
> midVal
) {
return BinarySearch(arr
, mid
+ 1, right
, findVal
);
} else {
return mid
;
}
}
}
递归两次找到
复杂度分析
最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
