二分圖判定c語言,二分查找c語言代碼

本文目錄一覽：

• 1、C語言 二分法查找次數公式怎麼推導？
• 2、在C語言中什麼是二分法
• 3、C語言二分查找法
• 4、C語言中的2分法是什麼意思 怎麼弄 例如這題

C語言 二分法查找次數公式怎麼推導？

  對具有n個元素的有序數組進行二分法查找，要分析的比較次數，可以使用畫二叉判定樹的方法來分析。該二叉判定樹的高度為[log2(n)]+1層，此即為二分查找的最多比較次數，比如：n=1000，則最多比較[log2(1000)]+1=9+1=10次。

  如果要計算平均的比較次數，則需要對二叉判定樹中的每個節點進行分析，處於第一層的比較1次，第二層的比較2次，第三層比較3次，依次類推……把各個節點的比較次數累加，再處於節點數（元素個數）即為平均比較次數，這裡假設查找是在等概率的情況下進行的。

  舉個例子：有9個元素的有序數組，對每個元素按1,2,3…8,9進行編號，則其二叉判定樹如下：

圖中可以看出，如果要找的元素處在第5個位置，則只要1次比較即可找到，若找第9個元素，則需要4次比較，算法分別比較了第5,7,8,9等4個元素。所以，平均的比較次數大概如下：

這樣分析，能看懂嗎？希望能幫到你！

在C語言中什麼是二分法

舉個例子吧，有一組有序數字，要查找某一數字，判斷中間數字是否符合條件，不符合再從中間分成兩半，選擇符合的一半，再判斷再分，直到找到或者不能再分為止。

注意一定是有序的，不能用於無序的數據查找。這樣每次都砍去一半，時間複雜度僅為lg(n),查找非常快。

C語言二分查找法

#include stdio.h

int binfind(int val[] , int num , int value)

{

int start = 0;

int end = num – 1;

int mid = (start + end)/2;

while(val[mid] != value start end)

{

if (val[mid] value)

{

end = mid – 1;

}

else if (val[mid] value)

{

start = mid + 1;

}

mid = ( start + end )/2;

}

if (val[mid] == value)

return mid;

else

return -1;

}

int main()

{

int nums[] = {1 , 3 , 4 ,7 ,8 , 12 ,45 ,67 ,97 ,123 ,456 ,675 ,1111 , 4534 , 4563};

int result = binfind(nums , sizeof(nums) / sizeof(nums[0]) , 45);

if (result 0)

{

printf(“查無此數”);

}

}

C語言中的2分法是什麼意思 怎麼弄 例如這題

) 用二分法求下面方程在（-10，10）之間的根。 2×3-4×2+3x-6=0【提示】(1) 取兩個不同點x1、x2,如果f(x1)和f(x2)符號相反，則(x1,x2)區間內必有一個根(曲線與x軸的交點)。如果f(x1)與f(x2)同符號，則應改變x1、x2，直到f(x1)、f(x2)異號為止。注意x1、x2的值不應相差太大，以保證(x1,x2)區間只有一根。

(2) x1和x2兩點之間的中點x=(x1+x2)/2,見圖4-1，再從x求出函數值f(x)。

(3) 若f(x)與f(x1)同符號，則根必在(x,x2)區間內，此時將x作為新的x1；如果f(x)與f(x2)同符號，則表示根在(x1,x)區間內，將x作為新的x2。

(4) 重複步驟(2)和(3)，直到|f(x)|ε為止，ε為一個很小的數。此時認為f(x)≈0，x即為根。

根據上述思路畫出N-S流程圖，如圖4-2所示。源程序命名為p5_8.c。

#include math.h

#include stdio.h

double fun(double x) { return 2 * x * x * x – 4 * x * x + 3 * x – 6; }

double root(double a, double b, double e)

{

double x1, x2, y1, x, y;

x1 = a; x2 = b;

do {

x = (x1 + x2)/2;

y = fun(x);

y1 = fun(x1);

if( ( y 0 y1 0) || (y 0 y1 0) )

x1 = x;

else

x2 = x;

/*end if*/

}while(fabs(y) e);

return x;

}

int main(void)

{

double x = root(-10.0f, 10.0f, 1e-8);

printf(“%f\n”, x);

return 0;

}