基础知识
log2为底数的算法是：
LOG2（N）
相当于2的多少次方（立方）等于N
例：LOG2（8）=3
相当于，2的3次方等于8
二分法
从排序好的数组，找到你需要找到的值（t=1），算法复杂度：O（log2(n)）
步骤：首先确认查找的数组索引范围，
1：假设数据int[] arr = {0,1,2,3,4,5,6,7,8,9};
2：则搜索范围为 [0,9]；即int start =0;int end = 9;
3：取数组索引中间的值跟t比较，int middle = （start + end）/2=4；
4：如果arr[middle]>t;则搜索范围控制在了（0，middle-1],即 end = middle-1;
相反，arr[middle]<t;则搜索范围控制在（middle+1，9],则 start = middle+1；
5：如果arr[middle]=t,搜索结束，否则就重复3，4。
写法
java
非递归写法
//二分法搜索算法
private Integer binary_search(int[] arr, int t) {
int start = 0, end = arr.length - 1;//扫描范围
while (start<=end){
int mid = (end + start) / 2;//中间数索引位置
if (t< arr[mid]){
end = mid-1;
}
if (t>arr[mid]){
start = mid+1;
}
if (t == arr[mid]){
return mid;
}
}
return null;
}
递归写法
public static int search(int num,int low,int high,int a[]) {
int middle = (high+low) / 2;
while(low<=high){
//注意等号要有
if(a[middle]>num){
return search(num, low, middle-1, a);
}else if(a[middle]<num){
return search(num, middle+1, high, a);
}else{
return middle;
}
}
return-1;
}
js
非递归写法
function binarySearch(arr,key){
var low=0; //数组最小索引值
var high=arr.length-1; //数组最大索引值
while(low<=high){
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key>arr[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
return -1; //low>high的情况，这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}
递归写法
function binarySearch(arr,low,high,key){
if(low>high){return -1;}
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key<arr[mid]){
high=mid-1;
return binarySearch(arr,low,high,key);
}else{
low=mid+1;
return binarySearch(arr,low,high,key);
}
}
站在巨人的肩膀上摘苹果:
链接：https://blog.csdn.net/u012194956/article/details/79103843
链接：https://blog.csdn.net/vacblog/article/details/80865715
链接: https://blog.csdn.net/dijiaxing1234/article/details/81178097