基本搜索算法-BinarySearch
In computer science,binary search is a search algorithm that finds the position of a target value within a sorted array
二分搜索算法
在对数组的搜索算法之中，最朴素的思想就是从数组的弟一个元素开始，逐个将数组中的元素与目标值作比较，以得到用户期望的元素下标，因此朴素的搜素算法是一种O(N)时间的方法。
二分搜素算法的基本思想：二分搜素算法每次将数组中间值与目标值相比较，若相同，则该元素就是要寻找的元素，若不相同，二分搜素发通告一定的方法抛弃一半的待搜索区间，在剩余的区间中继续以相同的方法搜索目标值，这也是‘二分’这个名字的由来，因此二分搜索算法是O(logN)时间的算法。
而在二分搜索算法的实现中，抛弃一半区间所依据的，是目标值与搜索区间中间值大小的比较，因此二分搜索算法要求数组是有序的，当目标值大于中间值时，抛弃小于中间值得一半区间，反之亦然。
- 二分搜索法
- 假设数组vec是待搜素数组（生序排列），target是目标值，且目前的搜索区间为[left,right）的左开右闭区间，那么则有mid为left与right的中值，即vec[mid]为当前搜索区间内的中间值
- 如果left==right说明当前搜索区间内无元素，返回搜索失败
- 将vec[mid]与target做比较
- 若target == vec[mid]则mid就是要查找的元素下标，返回mid
- 若target != vec[mid]则考虑target与vec[mid]在区间的前半部分，是right = mid并进入下一轮搜索
- 否则说明target在区间的后半部分，使left = mid+1并进入下一轮搜索
二分法算法实现
理解二分法原理后，可尝试自己实现一个二分法算法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public class BinarySearch {
public int binarySearch(int[] array,Integer target,Integer left,Integer right){
if(left.equals(right)){
return -1;//递归终点
}
int mid = left+(right-left)/2;//计算中间位置
//逻辑：搜索区域与目标值比较,若相等返回mid，否则抛弃一半的区间
if(target == array[mid]){
return array[mid];
}else if(target > array[mid]){
return binarySearch(array,target,mid,right);
}else if(target < array[mid]){
return binarySearch(array,target,left,mid);
}
return 0;
}
}
再回到开始的问题，Java数组中binarySearch有两种重载的方法：
- binarySearch(Object[],Object key)
方法的object[]参数是序查找的数组，key参数为要查找的key值
在key值找到的情况下：如果key在数组范围中，则从0开始计数，返回搜索值得索引。
在key值找不到的情况下：
[1]搜索值不是数组元素，且在数字的范围内，从1开始计数，得“-插入点索引值”；
[2]搜索值不是数组元素，且大于数组内的元素，索引值为-(length + 1)；
[3]搜索值不是数组元素，且小于数组内的元素，索引值为-1；
- binarySearch(Object[],int fromIndex,int toIndex,Object key)
方法的的object[]参数是序查找的数组，fromIndex参数为开始索引，toIndex为结束索引，索引参数构成一个[fromIndex,toIndex)区间，构成key参数为要查找的key值
在key值找到的情况下：如果key在数组中，则从0开始计数，返回数组的索引值；
在key值找不到的情况下：
[1]该搜索键在范围内，但不是数组元素，由1开始计数，得到“-插入点索引值”；
[3]该搜索键不在范围内，且大于范围内的元素，返回-（toIndex+1）
[4]该搜索键不在范围内，且小于范围内的元素，返回-（fromIndex+1）