1、顺序查找：在一个已知无序或有序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。
2、折半查找：它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关
顺序查找算法和折半查找算法的时间复杂度各是多少
假设对n个元素的折半查找需要消耗的时间为t(n)。容易知道：
如果n
=
1，则t(n)
=
c1
如果n
>
1，则t(n)
=
t(n/2)
+
c2
其中n/2需要取整，c1、c2都是常数
对于正整数n，可以有：
t(n)
=
t(n/2)
+
c2
=
t(n/4)
+
2c2
=
t(n/8)
+
4c2
=
=
t(n/(2的k次方))
+
kc2
一直推演下去，直到n/(2的k次方)等于1，也就是k
=
log2(n)，此时等式变为：
t(n)
=
t(1)
+
kc2
=
c1
+
log2(n)c2
于是时间复杂度为log2(n)。注意log2(n)和log(n)其实是同样的复杂度，因为它们之间仅仅差了一个常量系数而已。
这个是不严格的推导，因为没有考虑整数除以2之后可能有余数的情况。但即使有余数，也是不影响时间复杂度的。
什么是顺序查找什么是二分查找什么是对半查找
顺序
int find(int a[],int n,int x)//a[0]~a[n-1]的数组中，查询元素x，数据类型为int
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==x)
return i;//找到，返回编号
}
return -1;//找不到
}
折半查找
int binaryfind(int a[],int n,int x)//参数同上
{
int low,high,mid;
low=0;high=n-1;
while(low<=high)
{
mid=(low+high)/2;//计算中间位置
if(a[mid]==x) return mid;
if(a[mid]>x) high=mid-1;//假定a为递增数列
else low=mid+1;
}
return -1;//找不到
}
/
指定一个位置用该位置上的元素和数组元素进行比较。
在内循环结束一次，该位置出现最值。
/
public static void sort_1(int[] arr)
{
for(int x=0; x<arrlength-1; x++)
{
for(int y=x+1; y<arrlength; y++)
{
if(arr[x]>arr[y])
{
}
}
}
}
/
相邻两个元素进行比较。
内循环结束一次，后位出现最值。
/
public static void sort_2(int[] arr)
{
for(int x=0; x<arrlength-1; x++)
{
for(int y=0; y<arrlength-x-1;y++)
{
if(arr[y]>arr[y+1])
{
}
}
}
}
y<arrlength-x-1:
-x：为了减少参与比较的元素的个数。
-1：为了避免脚标越界。
public static void swap(int[] arr,int a,int b)
{
//arr[a] = arr[a]^arr[b];
//arr[b] = arr[a]^arr[b];
//arr[a] = arr[a]^arr[b];
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
//
}
4，折半查找:前提：必须是有序的数组才有效。
public static int binarySearch(int[] arr,int key)
{
int start=0,end=arrlength-1,mid;
while(start<=end)
{
mid = (start+end)>>1;
if(key>arr[mid])
start = mid + 1;
else if(key<arr[mid])
end = mid - 1;
else
return mid;
}
return -1;
}
相关推荐：
