一、什么是二分查找
二分查找是指在有序的数组中找到需要找的值。具体实现方式是，先取中间位置的值与需要查找的值进行比较，如果要查找的值小于中间的位置的值，则往左边继续取中间位置的值与要查找的值进行比较，如果要查找的值大于中间位置的值，则往右边继续取中间位置的值与其比较，如此循环，直到找到匹配的值为止。
二、实现方式--通过循环实现
public static int binarySearch(int[] ints , int value){
int low = 0;
int high = ints.length-1;
while(low<=high){
int middle = (low+high)/2;
//与中间位置的值进行比较
if(value==ints[middle]){
return middle;
}
else if(value<ints[middle]){
high = middle-1;
}
else{
low = middle+1;
}
}
return -1;
}
三、实现方式--递归实现
public static int binarySearch(int[] ints , int value , int low , int high){
if(value<ints[low]||value>ints[high]||low>high)
return -1;
int middle = (low+high)/2;
if(value == ints[middle]){
return middle;
}
else if(value<ints[middle]){
return binarySearch(ints , value , low , middle-1);
}
else{
return binarySearch(ints , value , middle+1 , high);
}
}
四、算法的介绍
1、算法的概念
算法是解决特定的问题实现步骤。
2、算法的设计原则
正确性、可读性、健壮性、高效率与低存储。
3、算法的特征
有穷性、正确性、可行性、有输入、有输出。
4、评价算法的指标
时间复杂度：运行一个程序所花费的时间。
空间复杂度：运行程序所需要的内存。
网友评论