二分法算法框架

㈠ 二分法原理是什么

二分法的原理：用传统的方法 要找到一个数字，需要for循环一个一个遍历，这种写法，如果在1000个数字中，找一个数组，需要遍历1000次，非常的消耗资源

所以提出了另一种方法 二分法，先对数组进行排序，找出中间的数，和查找的数进行对比；

二分法作用：常用于数据查找的方法； 前端的数组搜索；

案例：

var arr=[2,26,36,45,67,89,12,46,53,42];
//二分查找的前提，一定要从小到大排序；
arr.sort(function(a,b){
return a-b;
})
//最小的数的索引 ， 最大的书的索引；
var startindex=0;endindex=arr.length;
var findnum=prompt();
var middleindex=Math.floor((startindex+endindex)/2);
while(startindex!==middleindex&&endindex!==middleindex){
console.log(1);
if(arr[middleindex]>findnum){
endindex=middleindex;
}
else if(arr[middleindex]<findnum){
startindex=middleindex;
}
else if(arr[middleindex]==findnum){
break; //这里很重要，不然的话会一直遍历下去，因为是while循环 ，不加的话，很可能死机
}
middleindex=Math.floor((startindex+endindex)/2);
}
if(arr[middleindex]==findnum){
document.write("找到了");
}
else{
document.write("没找到");
}

㈡ 什么是二分法

二分法（Bisection method） 即一分为二的方法. 设[a，b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an，bn])：a0=a，b0=b，且对任一自然数n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中点。

(2)二分法算法框架扩展阅读

典型算法

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，

如果当前位置arr[k]值等于key，则查找成功；

若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；

若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，

直到找到为止,时间复杂度:O(log(n))。

㈢ 二分法是什么意思

二分法是数学领域术语。

二分法即，对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，

如果当前位置arr[k]值等于key，则查找成功；

若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；

若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，

直到找到为止，时间复杂度:O(log(n))。

C++语言中的二分查找法：

基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2。

1、开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。

2、令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。

3、令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。

如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。