学习算法第一步，看点入门书，比较推荐《图解算法》这本书
书中第一张介绍了二分查找法和简单查找法，我们分别用javascript,java,python来实现这种算法，二分查找法运行时间O（n)
javascript实现二分查找算法 在0~1024 查找100 计算了多少次
function init(length, index) {
if (index > length) {
console.log("输入的数值太大超出计算范围");
return
}
var intArr = [];
for (let i = 0; i < length; i++) {
intArr.push(i);
}
var count = 0;
function binarySearch(min, max, index) {
var milddel= Math.ceil((min + max) / 2);
count++;
if (index == milddel|| index == 0) {//防止栈溢出
return milddel
} else if (index < milddel) {
return binarySearch(min, milddel, index)
} else {
return binarySearch(milddel, max, index)
}
}
binarySearch(intArr[0], intArr[intArr.length - 1], index);
console.log("一共运算了" + count + "次");
}
init(1024, 100);
结果
python实现二分查找算法 在0~1024 查找11 计算了多少次
# -*- coding: UTF-8 -*-
count=0
def binarySearch(min,max,index):
milddel=(min+max)/2
global count
count+=1
if milddel==index or index==min:
return milddel
elif milddel<index:
binarySearch(milddel,max,index)
else:
binarySearch(min,milddel,index)
binarySearch(0,1024,11)
print("一共计算了"+str(count) +"次")
结果
java实现二分查找算法 在0~1024 查找1 计算了多少次
public class Binary {
int count=0;
int min;
int max;
public int getCount() {
return count;
}
public int binarySeach(int min, int max, int index){
int middle=(min+max)/2;
this.count++;
if(middle==index){
return middle;
}else if(middle
return binarySeach(middle,max,index);
}else{
return binarySeach(min,middle,index);
}
}
public static void main(String[] args){
Binary binary=new Binary();
int num=binary.binarySeach(0,1024,1);
System.out.println("一共计算"+binary.getCount()+"次");
}
}
结果
网友评论