本文目录
- 几种常见的查找算法之比较
- C++折半查找法
- 数据库复杂查询
- c语言中的折半查找法是什么原理
- 用C语言编写顺序查找和二分查找（折半查找）
- C++折半查找的基本思想和步骤
- 二分搜索算法是利用什么实现的算法
- JAVA 二分查找
- python 算法有哪些比赛
几种常见的查找算法之比较
一、顺序查找
条件：无序或有序队列。
原理：按顺序比较每个元素，直到找到关键字为止。
时间复杂度：O(n)
二、二分查找（折半查找）
条件：有序数组
原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度：O(logn)
三、哈希表（散列表）
条件：先创建哈希表（散列表）
原理：根据键值方式(Key value)进行查找，通过散列函数，定位数据元素。
时间复杂度：几乎是O(1)，取决于产生冲突的多少。
C++折半查找法
折半查找法是算法一种，可以被任何计算机语言使用。用C语言自然也可以实现。
1、定义：
在计算机科学中，折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
2、查找规则：
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l》h为止。如果l》h，说明没有此数，打印找不到信息，程序结束。
3、C语言参考代码：
int bin_search(int A,int n,int key){
//在长度为n的数组A 中折半查找值为key的元素，并返回下标值。如果不存在则返回-1.
int low,high,mid;
low = 0;
high = n-1;//初始low和high为数组的两端。
while(low《=high)
{
mid =(low + high)/2;//查找中心点。
if(A[mid]==key)return mid;//已找到，返回下标值。
if(A[mid]《key){//中点位置比key值小，以mid+1为新的下限值。
low =mid + 1;
}
if(A[mid]》key){//中点位置比key值大，以mid-1为新的上限值。
high= mid - 1;
}
}
return -1;//未找到，返回-1.
}
数据库复杂查询
数据库的查询功能实现原理：
数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
图1展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。
c语言中的折半查找法是什么原理
刚开始的时候数组时排好顺序的：从小到大，或者从大到小。然后将这个数组折中，用中间的这个数和要查找的数比较大小，（例如：如果我从小到大，我将数组这种后，用中间的数和要查找的数比较，如果小，则那个要查找的数绝对在中间靠左的范围里，如果大，则那个要查找的数绝对在中间靠右的范围里，然后同理，慢慢慢慢缩小范围，知道查找到为止）
用C语言编写顺序查找和二分查找（折半查找）
顺序查找：在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。复杂度为o(n).
二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n））
#include 《stdio.h》
//二分查找：
int search(int a,int x,int n) //x为要查找的元素，n为数组长度
{
int mid=0;
int low=0;
int high=n;
while(low《=high)
{
mid=(low+high)/2;
if(a[mid]==x)
{ return mid; }
else if(x《a[mid])
{ high=mid-1; }
else
{ low=high+1; }
}
return -1;
}
//顺序查找：
int search1(int a,int x,int n) //x为要查找的元素，n为数组长度
{
int i;
for(i=0;i《n;i++)
{
if(a[i]==x)
return i;
}
return -1;
}
int main()
{
int i,a,x;
for(i=0;i《10;i++)
scanf(“%d“,&a[i]);
printf(“请输入要查找的元素“);
scanf(“%d“,&x);
if(search(a,x,10)!=-1)printf(“查找的元素在数组中的位置为%d.\n“,search(a,x,10));
else printf(“该元素不在数组中\n“);
if(search1(a,x,10)!=-1)printf(“查找的元素在数组中的位置为%d.\n“,search1(a,x,10));
else printf(“该元素不在数组中\n“);
return 0;
}
C++折半查找的基本思想和步骤
折半查找法是效率较高的一种查找方法。
基本思想是：设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；
否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；
如此重复前面的过程直到找到或者l》h为止。如果l》h，说明没有此数，打印找不到信息，程序结束。
步骤：
1、首先确定整个查找区间的中间位置 mid=（ left + right） /2 。
2、用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功，若大于，则在后（右）半个区域继续进行折半查找，若小于，则在前（左）半个区域继续进行折半查找。
3、对确定的缩小区域再按折半公式，重复上述步骤。最后得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用一维数组存放。
扩展资料
折半查找法的优点：比较次数少，查找速度快，平均性能好；
缺点：是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
参考资料：百度百科-折半查找法
二分搜索算法是利用什么实现的算法
二分搜索算法是利用排除剩余元素中一半的元素实现的算法。
在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。
二分搜索算法原理：
1、如果待查序列为空，那么就返回－1，并退出算法；这表示查找不到目标元素。如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。如果不相等，就再比较这两个元素的大小。
2、如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。
3、如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。
JAVA 二分查找
二分查找原理，取一段已经排好序的数据段，先将该数据段从中间切割开，用需要查找的数据与该数据段的1/2处的数据进行比较，依此类推
如，有1-100数据，需要查找20，首先将100/2与20比较，20《100/2,在将100/2/2与20比较。。。。直到找出20，此方法操作速度较快，不过由于针对必须是已经排好序的数据段进行操作，使用较少，推荐冒泡法
JAVA中对数据段（数组，集合）进行操作的方法大多都封装与java.util.Collections;类下边，JAVA开源，楼主有兴趣可以去看看他的源码，算法相当之精辟，也可以与我进行交流，QQ：1101047
python 算法有哪些比赛
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。简单来讲，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。包括这几类：
1.
选择排序算法：选择排序是一种简单直观的排序算法。原理：首先在未排序序列中找到最小或最大元素，存放到排序序列的起始位置;然后，再从剩余未排序元素中继续寻找最大最小元素，然后放到已排序序列的后面，以此类推直到所有元素均排序完毕。
2.
快速排序算法：快速排序的运行速度快于选择排序。原理：设要排序的数组为N，首先任意选取一个数据作为关键数据，然后将所有比它小的数放到它前面，所有比它大的数都放到它后面，这个过程称之为快速排序。
3. 二分查找算法：二分查找的输入是一个有序的列表，如果要查找的元素包含在一个有序列表中，二分查找可以返回其位置。
4.
广度优先搜索算法：属于一种图算法，图由节点和边组成。一个节点可以与多个节点连接，这些节点称为邻居。它可以解决两类问题：第一类是从节点A出发，在没有前往节点B的路径;第二类问题是从节点A出发，前往B节点的哪条路径最短。使用广度优先搜索算法的前提是图的边没有权值，即该算法只用于非加权图中，如果图的边有权值的话就应该使用狄克斯特拉算法来查找最短路径。
5.
贪婪算法：又叫做贪心算法，对于没有快速算法的问题，就只能选择近似算法，贪婪算法寻找局部最优解，并企图以这种方式获得全局最优解，它易于实现、运行速度快，是一种不错的近似算法。
