查找是算法吗

Ⅰ 二叉树查找和二分查找是同一算法吗

两者的算法思路其实很像：比中间的小就在剩下的左边，大就在剩下的右边找
但是：
二叉树查找一般习惯是在链式存储上进行，为一个树形结构
二分查找一定在顺序存储上进行

Ⅱ 几种查找算法的比较

文章摘要: 查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，文中介绍四种查找算法，分别是顺序查找、二分查找、二叉排序树查找和哈希查找。并用JAVA语言编写了相应程序代码，比较了查找同一个数据的时间复杂度和空间复杂度。

Ⅲ 数据结构：重要的查找算法有哪些

折半查找也就是二分查找，它必须满足排序关系。
查找也可以用二叉查找树，一般复杂度为O(logn),最坏为O(n)。
也可用平衡树进行查找，如AVL,Treap,Splay等，可以做到保持O(logn)。

比二分查找性能更优的：大概只有Hash了吧。如果Hash函数设计的好，基本可以认为是O(1)

堆排序比较有意思，值得研究一下，理解了后，很有用～，也很重要。

Ⅳ 什么是查找法

算法思想：

将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。

折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。

算法步骤描述：

step1 首先确定整个查找区间的中间位置
mid = （ left + right ）/ 2

step2 用待查关键字值与中间位置的关键字值进行比较；

若相等，则查找成功

若大于，则在后（右）半个区域继续进行折半查找

若小于，则在前（左）半个区域继续进行折半查找
Step3 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。
折半查找的存储结构采用一维数组存放。

折半查找算法举例

对给定数列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。

折半查找的算法讨论：

优点: ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。

缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。

考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？

可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。

例如：[问题分析] 由于数据按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.

Java风格的代码举例：
//使用折半法进行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);

return nIndex;
}

二分查找的性能说明

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(n lg n) 的时间。
二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找

二分查找的C#实现代码：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失败
}
static void Main(string[] args)
{
Console.WriteLine("请输入10个递增数字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("数字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("请输入一个你要查找的数字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}

分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，确定待查项X所在的子表（块）。
（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。

Ⅳ 查找算法的概念

用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。分块查找也称为索引查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键字值的大小有序排列，还要建立一个按关键字值递增顺序排列的索引表，索引表中的一项对应线形表中的一块，索引项包括两个内容：① 键域存放相应块的最大关键字；② 链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待查找的结点属于哪一块，然后在块内查找结点。哈希表查找是通过对记录的关键字值进行运算，直接求出结点的地址，是关键字到地址的直接转换方法，不用反复比较。假设f包含n个结点，Ri为其中某个结点（1≤i≤n），keyi是其关键字值，在keyi与Ri的地址之间建立某种函数关系，可以通过这个函数把关键字值转换成相应结点的地址，有：addr(Ri)=H(keyi)，addr(Ri)为哈希函数。

Ⅵ 查找的计算机算法

⒈顺序查找的思想是：
将查找值顺序逐个与结点值进行比较，相等即为查找成功，否则查找失败.
程序如下：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
b:boolean;
place:integer;
procere search(r:arr;m,x:integer; var found:boolean;var p:integer);
begin
p:=1;found:=false;
while(p<=m) and not found do
if r[p]=x then found:=true else p:=p+1;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
search(a,n,x1,b,place);
if b then begin writeln('yes');writeln('Place of',x1:5,'is:',place); end
else writeln('no');
end. ⒈二分查找的基本思想：首先将结点按关键字排序，其次将查找值与中间位置的值比较，相等，查找成功；不等，则中间数据大于或小于查找值，无论怎样查找将在一半的数据中查找。
⒉例：输入序列数据查找指定值.
程序：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
place:integer;
procere paixv(var r:arr;m:integer);
var k,j,i,t:integer;
begin
k:=m;
while k>0 do
begin
j:=k-1;k:=0;
for i:=1 to j do
if r[i]>r[i+1] then
begin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end;
end;
end;
procere search(r:arr;m,x:integer; var p:integer);
var low,high,mid:integer;
begin
p:=0;low:=1;high:=m;
while low<=high do
begin
mid:=(low+high) div 2;
if x>r[mid] then low:=mid+1 else
if x<r[mid] then high:=mid-1 else
begin p:=mid;exit;end;
end;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
paixv(a,n);
search(a,n,x1,place);
if place<>0 then writeln('yes') else writeln('no');
end. 因为二叉排序树的左子树若不为空则左子树的所有结点的值均小于它的根结点的值，而右子树若不为空，则右子树的所有结点的值均不小大于它的根结点的值，根据这个性质查找算法如下：
program pxtree;
const
a:array[1..8] of integer=（10,18,3,8,12,2,7,3）；
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i,x:integer;
procere maketr(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then maketr(d,right) else maketr(d,left);
end;
function searchtr(x:integer;p:point):boolean;
begin
if p=nil then searchtr:=false
else if x=p^.w then searchtr:=true
else if x<p^.w then searchtr:=searchtr(x,p^.left)
else searchtr:=searchtr(x,p^.right);
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do maketr(a[i],first);
write('want find data x:');read(x);
if searchtr(x,first) then writeln('yes') else writeln('No');
end. 以上讲的查找方法基于比较的，查找效率依赖比较次数，其实理想的查找希望不经比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，这样查找k时，只要根据这个对应关系f找到给定值k的像f(k）。这种对应关系f叫哈希（hash）函数。按这种思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存储时容易冲突（collision）：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。
⒈哈希函数的构造方法
直接寻址法：H(k)=k 或H(k)=a*k+b（线形函数）
如：人口数字统计表 地址 1 2 3 ... 100 年龄 1 2 3 ... 100 人数 67 3533 244 ... 4 数字分析法：取关键字的若干数位组成哈希地址
如：关键字如下：若哈希表长为100则可取中间两位10进制数作为哈希地址。 81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537 平方取中法：关键字平方后取中间几位数组成哈希地址
折叠法：将关键数字分割成位数相同的几部分（最后一部分的位数可以不同）然后取几部分的叠加和（舍去进位）作为哈希地址。
除留余数法：取关键字被某个不大于表长m的数p除后所得的余数为哈希地址。
H(k)=k mod p p<=m
随机数法：H(k)=rondom(k）。
⒉处理冲突的方法
假设地址集为0..n-1，由关键字得到的哈希地址为j(0<=j<=n-1）的位置已存有记录，处理冲突就是为该关键字的记录找到另一个空的哈希地址。在处理中可能得到一个地址序列Hi i=1，2，...k
0<=Hi<=n-1），即在处理冲突时若得到的另一个哈希地址H1仍发生冲突，再求下一地址H2，若仍冲突，再求H3...。怎样得到Hi呢？
开放寻址法：Hi=(H(k)+di) mod m （H(k）为哈希函数；m为哈希表长；di为增量序列）
当di=1，2，3，... m-1 时叫线性探测再散列。
当di=1，-1，2，-2，3，-3，...,k,-k时叫二次探测再散列。
当di=random（m）时叫伪随机探测序列。
例：长度为11的哈希表关键字分别为17，60，29，哈希函数为H(k)=k mod 11，第四个记录的关键字为38，分别按上述方法添入哈希表的地址为8，4，3（随机数=9）。
再哈希法：Hi=RHi(key) i=1,2,...,k，其中RHi均为不同的哈希函数。
链地址法：这种方法很象基数排序，相同的地址的关键字值均链入对应的链表中。
建立公益区法：另设一个溢出表，不管得到的哈希地址如何，一旦发生冲突，都填入溢出表。
⒊哈希表的查找
例：如下一组关键字按哈希函数H(k)=k mod 13和线性探测处理冲突所得的哈希表a[0..15]: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 当给定值k=84，则首先和a[6]比在依次和a[7],a[8]比结果a[8]=84查找成功。
当给定值k=38，则首先和a[12]比，再和a[13]比，由于a[13]没有，查找不成功，表中不存在关键字等于38的记录。 查找第k小元素即在n个元素中（未排序）找到第k小的元素。方法同快速排序，采用递归方式。
程序如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b[s] else
begin
p1:=p(s,t);
q:=p1-s+1;
if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b[i]);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find（1,n,k));
end.

Ⅶ 查找算法有哪些

查找算法常用的有，顺序查找，二分查找，哈希表查找，等等。

Ⅷ 几种常见的查找算法之比较

二分法平均查找效率是O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用O（nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需要移动整个数组，所以动态的情况下比较慢。

哈希查找理想的插入和查找效率是O(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表需要较大的空间，至少要比O(n)大几倍，否则产生冲突的概率很高。

二叉排序树查找也是O(logn)的，关键是插入值时需要做一些处理使得它较为平衡（否则容易出现轻重的不平衡，查找效率最坏会降到O(n)），而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是c语言，直接利用它的库类型map、multimap就可以了,它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的二叉平衡树稍微慢一些。

Ⅸ 查找算法和枚举算法差别

不对
枚举是在范围内查找所有可能解，不是找到就结束；
顺序查找是假设在数组范围内找key，找到就结束，不一定到数据结束。也就是，如果数组中的第一个数据就是我们要找的key，那么找到了，不再继续找第2个。

Ⅹ 常见查找和排序算法

查找成功最多要n 次，平均（n+1）/2次， 时间复杂度为O(n) 。
优点：既适用顺序表也适用单链表，同时对表中元素顺序无要求，给插入带来方便，只需插入表尾即可。
缺点：速度较慢。

改进：在表尾设置一个岗哨，这样不用去循环判断数组下标是否越界，因为最后必然成立。

适用条件：

二分查找的判定树不仅是二叉排序树，而且是一棵理想平衡树。 时间复杂度为O(lbn) 。

循环实现

递归实现

待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 ~N2/2 次比较和 ~N 次交换，==它的运行时间与输入无关==，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

从左到右不断 交换相邻逆序的元素 ，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

每次都 将当前元素插入到左侧已经排序的数组中 ，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

==插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低==。

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并方法将数组中两个已经排序的部分归并成一个。

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

先归并那些微型数组，然后成对归并得到的微型数组。

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 大的元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

将新元素放到数组末尾，然后上浮到合适的位置。

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，==计数排序要求输入的数据必须是有确定范围的整数==。

当输入的元素是 n 个 0 到 k 之间的整数时，它的==运行时间是 O(n + k)==。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。比较适合用来排序==小范围非负整数数组的数组==。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

当输入数据均匀分配到每一个桶时最快，当都分配到同一个桶时最慢。

实间复杂度N*K

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。