C语言中的2分法是什么意思 如何弄 例如这题
C语言中的2分法是什么意思 怎么弄 例如这题
（4） 将20个数存放在一个数组中，首先使用选择法对这20个数按升序排列，并输出排序后的结果；然后从键盘输入一个数，要求用二分查找的方法找出该数在数组中的位置（即下标），如果该数不在数组中，则输出“无此数”。
提示：首先利用一个二重循环实现选择排序；然后使用单重循环来实现二分查找。
测试实例：
输入： 100 10 -125 -9 0 90 70 60 300 -250 -72 39 48 22 83 159 142 -129 -24 539
输出：-250 -129 -125 -72 -24 -9 0 10 22 39 48 60 70 83 90 100 142 159 300 539
输入： -129
输出： 17
输入： 301
输出： 无此数
------解决思路----------------------
不知道楼主还记不记得,高中时候 的二分法求解方程近似解.
------解决思路----------------------
For reference only
------解决思路----------------------
思路如下：
排序后，因为升序排列，所以元素值大的对应的下标大，即下标从0~19，而元素值也依次增大，可以先选取【0】跟【19】对应的元素值，Avr = (a[0]+a[19])/2，如果当前要比较的数值Cur_data < Avr，那么说明Cur_data在下标【0】~【19】之间，因此，继续比较，取【0】跟【10】，如果Avr < (a[0] + a[10])/2 ，说明Avr在这个区间之内....依此下去，就会找到Cur_data对应的位置
------解决思路----------------------
（4） 将20个数存放在一个数组中，首先使用选择法对这20个数按升序排列，并输出排序后的结果；然后从键盘输入一个数，要求用二分查找的方法找出该数在数组中的位置（即下标），如果该数不在数组中，则输出“无此数”。
提示：首先利用一个二重循环实现选择排序；然后使用单重循环来实现二分查找。
测试实例：
输入： 100 10 -125 -9 0 90 70 60 300 -250 -72 39 48 22 83 159 142 -129 -24 539
输出：-250 -129 -125 -72 -24 -9 0 10 22 39 48 60 70 83 90 100 142 159 300 539
输入： -129
输出： 17
输入： 301
输出： 无此数
------解决思路----------------------
不知道楼主还记不记得,高中时候 的二分法求解方程近似解.
------解决思路----------------------
For reference only
#include<stdio.h>
/*选择排序*/
void select_sort(int *arry, int len)
{
int i,j,tmp;
for(i = 0; i < len; ++i)
for(j = i+1; j < len; ++j)
{
if( arry[j] < arry[i])
{
tmp = arry[i];
arry[i] = arry[j];
arry[j] = tmp;
}
}
}
/*二分查找*/
int binary_search(int *arry, int len, int key)
{
int low = 0,high = len - 1 ;
int mid = (low + high) / 2;
while(low < high)
{
if(arry[mid] == key)
return mid;
else if(arry[mid] < key)
{
low = mid + 1 ;
mid = (low + high) / 2;
}
else
{
high = mid - 1;
mid = (low + high) / 2;
}
}
/*数组中没有key*/
return -1;
}
int main()
{
int test[20];
int i;
printf("输入:");
for(i = 0; i < 20; ++i)
{
scanf("%d",&test[i]);
}
/*选择排序*/
select_sort(test,20);
printf("输出:");
for(i = 0; i < 20; ++i)
{
printf("%d ",test[i]);
}
while(1)
{
char ch;
int n;
int key;
printf("输入:");
scanf("%d",&key);
n = binary_search(test,20,key);
if(n >= 0)
{
printf("输出:%d\n",n);
break;
}
else
{
printf("输出: 无此数\n");
}
}
}
------解决思路----------------------
思路如下：
排序后，因为升序排列，所以元素值大的对应的下标大，即下标从0~19，而元素值也依次增大，可以先选取【0】跟【19】对应的元素值，Avr = (a[0]+a[19])/2，如果当前要比较的数值Cur_data < Avr，那么说明Cur_data在下标【0】~【19】之间，因此，继续比较，取【0】跟【10】，如果Avr < (a[0] + a[10])/2 ，说明Avr在这个区间之内....依此下去，就会找到Cur_data对应的位置
------解决思路----------------------