二分法演算法框架

㈠ 二分法原理是什麼

二分法的原理：用傳統的方法 要找到一個數字，需要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的情況，表示查找不成功。