二分法查找的介绍？c语言中如何将顺序表排序并实现二分法查找

本文目录

• 二分法查找的介绍
• c语言中如何将顺序表排序并实现二分法查找
• 二分法查找为什么只适用于顺序存储
• 二分查找的平均查找长度
• 二分法查找500需要几次
• C语言 二分法查找次数公式怎么推导
• 二分法检索如何进行
• 二分查找的查找长度是多少
• 使用二分法查找算法的 前提条件是 被查数据必须是自然数对吗
• C语言用二分法查找关键字

二分法查找的介绍

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。主要思想是：（设查找的数组区间为array。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半。递归找，即可，时间复杂度:O(log2n)。

c语言中如何将顺序表排序并实现二分法查找

void InsertSort(sq R)

这个函数是按值传递参数的。换句话说，你的顺序表在传递的时候被复制了一遍，然后这个函数收到的是一个副本，然后这个程序也许成功排序了这个副本，但是你原来的顺序表并没有改变。你可以考虑传递这个顺序表的指针。比如这样

void InsertSort(sq *pR)
{
    sq R = *pR;
    //以下不变
    ...
 }

调用的时候传递R的地址

InsertSort(&R);

二分法查找为什么只适用于顺序存储

二分查找法只适用于顺序存储，而且只适用于有序序列。

顺序存储是指用一段地址连续的存储单元存储相邻数据元素，比如我们常用的数组。这是一个物理上的概念。和它相对的是链式存储。

有序序列是指一个序列中的所有元素已经按照某种确定的方式排好了序，比如最简单的 int 数组的由小到大（或由大到小）。这是一个逻辑上的概念。

二分查找法指的是在有序的序列中查找某一元素，利用该序列已经有序的特点，每次比较范围中间的元素与目标元素的大小，即可确定目标值在中间值的前面还是后面，这样每次比较都能把查找范围缩小一半，达到快速查找的目的。

很显然，适用二分查找法的序列要满足两个条件：一是该序列内的元素是有序排列的(这很显然)；二是该序列能够让程序直接访问它范围中间的元素，也就是需要能够随机存取。

我们知道链式存储是不支持随机存取的，比如一个单链表，我们想访问其中的第几个元素，就得从头结点开始一个一个往后查找，这种情况下非要用二分查找法实在是逆大天。

上面看完如果还是不太理解的话，我们可以具体分析一下：

二分查找本身是 T(logN)

对于顺序存储，随机存取是 T(1)，不管你多长，给个下标我就飞过去了。那么顺序存储二分查找法的时间复杂度就是 O(logN)。

对于单链表，访问中间元素就得从头开始，把前面一半的结点都走一遍，T(N/2)。那么单链表二分查找法的时间复杂度就达到了 O(NlogN)，要知道最简单的直接查找也就 O(N) 。

那么双向链表呢？也没有好到哪去，双向链表做二分查找法的时间复杂度也是 O(N)，在某些情况下会比直接查找快一些，但仅此而已了。

至于二叉树等结构，由于已经不属于线性存储结构，这里就不讨论。

二分查找的平均查找长度

1. 平均查找长度=1/12*(1*1+2*2+3*4+4*5)=37/12。

2. 关于有序线性表是说线性表中的元素是按照升序或降序（允许相邻元素相同）的方式排列的。线性表是一种基本的计算机内的存储工具。
   

3. 顺序查找的基本思想是：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。

4. 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。

5. 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。

6. 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
   

二分法查找500需要几次

如果是线性查找的话是500次,而二分法查找则最多只需要10次。10000是14次,100000是17次……至于这最多次数是怎么算出来的,大家...

C语言 二分法查找次数公式怎么推导

    对具有n个元素的有序数组进行二分法查找，要分析的比较次数，可以使用画二叉判定树的方法来分析。该二叉判定树的高度为+1=9+1=10次。

    如果要计算平均的比较次数，则需要对二叉判定树中的每个节点进行分析，处于第一层的比较1次，第二层的比较2次，第三层比较3次，依次类推……把各个节点的比较次数累加，再处于节点数（元素个数）即为平均比较次数，这里假设查找是在等概率的情况下进行的。

    举个例子：有9个元素的有序数组，对每个元素按1,2,3...8,9进行编号，则其二叉判定树如下：

图中可以看出，如果要找的元素处在第5个位置，则只要1次比较即可找到，若找第9个元素，则需要4次比较，算法分别比较了第5,7,8,9等4个元素。所以，平均的比较次数大概如下：

这样分析，能看懂吗？希望能帮到你！

二分法检索如何进行

二分法检索
二分法检索要求线性表结点按关键码值排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较高，设线性表有n个元素，则最多的检索次数为大于log2
n
的最小整数，最少的检索次数为1。
二分法检索又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组中，首先将给定值key与字典中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在字典前半部分中继续进行二分法检索，若key大，则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。二分法检索是一种效率较高的检索方法，要求字典在顺序表中按关键码排序。

二分查找的查找长度是多少

以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为4。

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找的时间复杂度是O（2为底的log(n)），也就是说它的平均查找长度只和该有序表的长度有关，当长度为10时，平均查找长度为log10（2为底），其》3，《4，所以平均查找长度为4次。

扩展资料：

二分查找的查找过程：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

使用二分法查找算法的 前提条件是 被查数据必须是自然数对吗

前提是被查数据必须有序(升序或降序)。

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

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

若key大于当前位置值arr，直到找到为止,时间复杂度:O(log(n))。

扩展资料：

给定精确度ξ,用二分法求函数f(x)零点近似值的步骤如下:

1、确定区间,验证f(a)·f(b)《0,给定精确度ξ。

2、求区间(a,b)的中点c。

3、计算f(c).

(1) 若f(c)=0,则c就是函数的零点。

(2) 若f(a)·f(c)《0,则令b=c。

(3) 若f(c)·f(b)《0,则令a=c。

(4) 判断是否达到精确度ξ:即若|a-b|《ξ,则得到零点近似值a(或b),否则重复2-4。

C语言用二分法查找关键字

#include《stdio.h》
#include《stdlib.h》
#define Size 15
int main()
{
int binarySearch(int , int, int, int);
void printHeader(void);
void printRow(int ,int,int,int);
int a,i,key,element;
for(i=0;i 《= Size-1;i++)
a=2*i;
printf("Enter a number between 0 and 28:");
scanf("%d",&key);
printHeader();
element=binarySearch(a, key, 0, Size-1);
if(element!=-1)
printf("\n%d found in array element %d !\n",key,element);
else
printf("\n%d is not found!\n",key);

system("pause");
}
void printHeader()
{
int i;
printf("\nSubscripts:\n");
for(i=0;i《=Size-1;i++)
printf("%3d",i);
printf("\n");
for(i=1;i《=4*Size;i++)
printf("-");
printf("\n");
}
int binarySearch(int array, int searchKey, int low, int high)
{
void printRow(int array,int low,int middle,int high);
int middle;
while(low《=high){
middle=(low+high)/2;
printRow(array,low,middle,high);
if(searchKey==array)
return middle;
else if(searchKey《array)
high=middle-1;
else
low=middle+1;
}
return -1;
}
void printRow(int array,int low,int middle,int high)
{
int i;
for(i=0;i《=Size-1;i++)
if(i《low||i》high)
printf(" ");
else if(i==middle)
printf("%3d*",array);
else
printf("%3d",array);
printf("\n");
}
效率分析：线型查找摆脱了数组排序的约束，不足之处是不适合大型数据查找，并且查找方法比较老套，如果要找的数是数组中最后一个数n，那么搜索从0开始，一直检索到n，要经过n次遍历，时间复杂度：O(n)，而二分查找法中如果查找关键字小于数组中间的元素，就查找数组的头半部分，否则查找数组的后半部分，时间复杂度：O(log2N)，如果在指定子数组中还没有查找到关键字，就再把子数组折半，反复进行这种查找，直到要查找的关键字等于子数组中间的元素，或没有找到关键字为止。在最坏的情况下，用二分法查找有1024个元素的数组也只需要比较10次，即用2除1024，连续除10次得到1为止，如果有1048576（2的20次方）个元素，用二分法只要比较20次就可以找到要查找的元素，而用简单的线型查找则需要进行2的20次方查找，可见二分法比线型查找法的效率要高得多，对10亿个元素的数组来说，平均比较5亿次和30次简直是天壤之别！所以掌握二分法对在庞大的数组库处理是很有效的！