前提条件:一个有序的数组
const arr=[ 33, 44, 55, 55, 78, 88, 99, 101, 110, 115, 120, 125, 130, 140, 150, 166 ];
问题:查找其中是否包含指定数字n?
解决方法1.
用普通查找法,算法复杂度O(n).
const normal_search = (arr,n)=>{
let i=0;
while (i<arr.length){
console.log("普通查找走了一次",i,arr[i],n);
if(arr[i]===n){
return i
}
i+=1;
}
return -1
};
console.log("普通查找",arr,normal_search(arr,99));
解决方法2.
用二分查找法,算法复杂度O(log n).
const binary_search=(arr,n)=>{
const binary_search_copy=(arr,n,start,end)=>{
console.log("二分查找走了一次");
if(arr.length<1){return -1};
let middle = Math.floor((start+end)/2);
if(n===arr[middle]){
return middle
}else if(n<=arr[middle]){
return binary_search_copy(arr,n,start,middle-1)
}else if(n>arr[middle]){
return binary_search_copy(arr,n,middle+1,end)
}
};
return binary_search_copy(arr,n,0,arr.length)
};
console.log("二分查找",arr,binary_search(arr,99)); // 6
console.log("二分查找",arr,binary_search(arr,166)); // 15