[Java算法系列教程]-二分查找算法
二分查找算法
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
算法
- 假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;
- 否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
- 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
算法要求
- 必须采用顺序存储结构。
- 必须按关键字大小有序排列。
复杂度
时间复杂度
折半搜索每次把搜索区域减少一半,时间复杂度为 O(logn)。(n代表集合中元素的个数)
空间复杂度
O(1)。虽以递归形式定义,但是尾递归,可改写为循环。
代码示例
java
循环
public static int binarySearch(int[] arr, int start, int end, int hkey){
int result = -1;
while (start <= end){
int mid = start + (end - start)/2;
if (arr[mid] > hkey)
end = mid - 1;
else if (arr[mid] < hkey)
start = mid + 1;
else {
result = mid ;
break;
}
}
return result;
}
递归
public static int binarySearch(int[] arr, int start, int end, int hkey){
if (start > end)
return -1;
int mid = start + (end - start)/2;
if (arr[mid] > hkey)
return binarySearch(arr, start, mid - 1, hkey);
if (arr[mid] < hkey)
return binarySearch(arr, mid + 1, end, hkey);
return mid;
}
python
def binary_search(arr, start, end, hkey):
if start > end:
return -1
mid = start + (end - start) / 2
if arr[mid] > hkey:
return binary_search(arr, start, mid - 1, hkey)
if arr[mid] < hkey:
return binary_search(arr, mid + 1, end, hkey)
return mid