有序数组查找算法

⑴ 查找算法：采用二分法在有序数组 中查找一数，指出数的位置和查找次数。

#include<iostream>
usingnamespacestd;

voidBinarySearch(int*list,intlen,intkey,int*index_t){
	//最低边界
	intlow=0;
	//最高边界
	inthigh=len-1;
	while(low<=high){
		index_t[0]++;
		//取中间值
		intmiddle=(low+high)/2;
		if(list[middle]==key){
			index_t[1]=middle;
			return;
		}
		elseif(list[middle]>key){
			//下降一半
			high=middle-1;
		}
		else{
			//上升一半
			low=middle+1;
		}
	}
	//没找到
	index_t[1]=-1;
}

intmain(){
	constintN=10;
	intlist[N]={3,9,11,12,21,23,56,61,89,98};
	intindex_t[2]={0};
	BinarySearch(list,N,12,index_t);
	
	cout<<"查找次数为:"<<index_t[0]<<endl;
	if(index_t[1]!=-1)
		cout<<"已经找到12,索引位置为:"<<index_t[1]<<endl;
	else
		cout<<"没找到!"<<endl;
}

⑵ 在一个有序的数列中查找一某一数据项，使用顺序、插入、二分法三种算法来编程实现，其效率的高低排序是

打个比方，比如数组有100个元素，找出中间的元素，也就是第50个元素，和你输入的整数做比较大小。如果整数小，就在0-50元素中再找中间元素，如果整数大，就在51-100元素中找中间元素。依此类推，最终能找到整数在数组中的位置。

⑶ C++有序数组查找问题

二分法查找算法，数据结构应该学的，随手写个代码如下：
int binsearch(int *a, int length, int key)
{
int low=0;
int high = length-1;
if(a[low]==key)
{
return low;
}
if(a[high]==key)
{
return high;
}
while(low<=high)
{
mid=low+(high-low)/2;
if(a[mid]==key)
{
return mid;
}
if(a[mid]>key)
{
high = mid-1;
}
else
{
low = mid+1;
}
if(low>high)
return -1;
}
}

⑷ 找两个有序数组的中位数的几种方式

我用5个思路的来解决两个非减序数组的中位数.但是成功的只有四个,思路3边界问题太严重.
有时间再来弄好他,他在考试中也不适合使用(边界问题没法快速解决,网上也有人说小数据枚举法确定边界),总的来说费事.

主函数:

#include<stdio.h>
#include<time.h>
#include<limits.h>

doublefindMedianSortedArrays_1(int*nums1,intnums1Size,int*nums2,intnums2Size);
doublesss(inta[],intm,intb[],intn,intk);
doublefindMedianSortedArrays_2(int*nums1,intnums1Size,int*nums2,intnums2Size);
doublefindMedianSortedArrays_3(int*nums1,intnums1Size,int*nums2,intnums2Size);
doublefindMedianSortedArrays_4(int*nums1,intnums1Size,int*nums2,intnums2Size);
doublefindMedianSortedArrays_5(int*nums1,intnums1Size,int*nums2,intnums2Size);

intmain(){
	clock_tstart_t,end_t;
	doubletotal_t;
	doublemid=0;
//			1234567891011
	intstr1[1000]={0,2,4,5,7,9,10,15,21,23,25},
	str2[1000]={5,6,9,15,17,18,20,23,24,26,27,29,50};
//			12345678910111213
	start_t=clock();
	mid=findMedianSortedArrays_1(str1,11,str2,13);
	end_t=clock();
	total_t=(double)((double)end_t-(double)start_t)/CLOCKS_PER_SEC;
	printf("方法1:CPU占用的总时间：%fns
",(total_t*1000000000));
	printf("中位数%f
",mid);

	start_t=clock();
	mid=findMedianSortedArrays_2(str1,11,str2,13);
	end_t=clock();
	total_t=(double)((double)end_t-(double)start_t)/CLOCKS_PER_SEC;
	printf("方法2:CPU占用的总时间：%fns
",(total_t*1000000000));
	printf("中位数%f
",mid);

	start_t=clock();
	mid=findMedianSortedArrays_3(str1,11,str2,13);
	end_t=clock();
	total_t=(double)((double)end_t-(double)start_t)/CLOCKS_PER_SEC;
	printf("方法3:CPU占用的总时间：%fns
",(total_t*1000000000));
	printf("中位数%f
",mid);

	start_t=clock();
	mid=findMedianSortedArrays_4(str1,11,str2,13);
	end_t=clock();
	total_t=(double)((double)end_t-(double)start_t)/CLOCKS_PER_SEC;
	printf("方法4:CPU占用的总时间：%fns
",(total_t*1000000000));
	printf("中位数%f
",mid);

	start_t=clock();
	mid=findMedianSortedArrays_5(str1,11,str2,13);
	end_t=clock();
	total_t=(double)((double)end_t-(double)start_t)/CLOCKS_PER_SEC;
	printf("方法5:CPU占用的总时间：%fns
",(total_t*1000000000));
	printf("中位数%f
",mid);

	return0;
}

思路一:

/*
方法1:采用归并两个非减数组形成新非减数组,然后求取新数组的中位数.
性能分析:归并两数组的时间复杂度O(n+m),查找中位数时间复杂度O(1).所以时间复杂度O((n+m)*1)=O(m+n)
*/
doublefindMedianSortedArrays_1(int*nums1,intnums1Size,int*nums2,intnums2Size){
	inti=0,j=0,k=0;
	intc[10000]={0};
	doublemid_f=(nums1Size+nums2Size);
	intsign=(!((int)mid_f&0x1));
	if((!nums1Size)&&(!nums2Size))return-1;
	/*mid_f=(mid_f/2);
	if(nums1Size==0){
		return((nums2[(int)mid_f]+nums2[(int)(mid_f-sign)])/2);
	}
	if(nums2Size==0){
		return((nums1[(int)mid_f]+nums1[(int)(mid_f-sign)])/2);
	}*/
	while((i<nums1Size)&&(j<nums2Size))
	{
		c[k++]=(nums1[i]<=nums2[j])?nums1[i++]:nums2[j++];
	}
	while(i<nums1Size)
	{
		c[k++]=nums1[i++];
	}
	while(j<nums2Size)
	{
		c[k++]=nums2[j++];
	}
	//mid_f=(k&0x1)?(c[(k/2)]):(((c[(k/2+sign)])+(c[(k/2)]))/2);
	mid_f=(((c[(k/2-sign)])+(c[(k/2)]))/2);
	
	printf("OKk=%d(nums1Size+nums2Size)=%di=%dj=%d
",k,(nums1Size+nums2Size),i,j);
	i=0;
	while(i<=k)
	{
		printf("c[%d]=%d
",i,c[i]);
		i++;
	}
	
	returnmid_f;
}

思路二:

/*
用统计方法,从小到大对两数组同时进行归并式的遍历,并计数.当计数值等于两数组的中位数的下标,就找到中位数.
性能分析:时间复杂度是归并时间复杂度的一半,即O(m+n)=O((m+n)/2)
*/
doublefindMedianSortedArrays_5(int*nums1,intnums1Size,int*nums2,intnums2Size){
inti=0,j=0,k=0;
intmiddle=(nums1Size+nums2Size);
doublesign=(!(middle&0x1));
if((nums1Size==0)&&(nums2Size==0))return-1;
middle=(middle/2);
if(nums1Size==0){
return((nums2[(int)middle]+nums2[(int)(middle-sign)])/2);
}
if(nums2Size==0){
return((nums1[(int)middle]+nums1[(int)(middle-sign)])/2);
}
if(sign){
for(i=0,j=0,k=0;i<=(int)(middle-sign);i++)
{
(nums1[j]<=nums2[k])?(nums1[(j++)]):(nums2[k++]);
}
middle=(nums1[j]<=nums2[k])?(nums1[j--]):(nums2[k--]);//偶数中位数的前半部分最大值
middle=((middle+((nums1[j]<=nums2[k])?(nums1[j]):(nums2[k])))/2);//[偶数中位数的后半部分最小值+middle(偶数中位数的前半部分最大值)]/2=middle
}
else
{
for(i=0,j=0,k=0;i<=(middle-sign);i++)
{
(nums1[j]<=nums2[k])?(nums1[(j++)]):(nums2[k++]);
}
middle=(nums1[j]<=nums2[k])?(nums1[j]):(nums2[k]);
}
returnmiddle;
}

测试结果:(出现的特例:这着实具有不可避免性.输入全体样本中重复率高时,结束条件能被错误触发.)

/*

OK k = 24 (nums1Size + nums2Size) = 24 i = 11 j = 13

c[0] = 0

c[1] = 2

c[2] = 4

c[3] = 5

c[4] = 5

c[5] = 6

c[6] = 7

c[7] = 9

c[8] = 9

c[9] = 10

c[10] = 15

c[11] = 15

c[12] = 17

c[13] = 18

c[14] = 20

c[15] = 21

c[16] = 23

c[17] = 23

c[18] = 24

c[19] = 25

c[20] = 26

c[21] = 27

c[22] = 29

c[23] = 50

c[24] = 0

方法1:CPU 占用的总时间：4000000.000000 ns

中位数 16.000000

方法2:CPU 占用的总时间：0.000000 ns

中位数 16.000000

nums1Size = 11 nums1[5] = 9 nums2Size = 13 nums2[6] = 20

nums1Size = 6 nums1[3] = 21 nums2Size = 7 nums2[3] = 15

nums1Size = 4 nums1[2] = 15 nums2Size = 4 nums2[2] = 18

nums1Size = 2 nums1[0] = 15 nums2Size = 3 nums2[1] = 17

nums1Size = 2 nums1[0] = 15 nums2Size = 2 nums2[0] = 15

方法3:CPU 占用的总时间：15000000.000000 ns

中位数 15.000000

la = 9 ra = 9 lb = 20 rb = 20

la = 21 ra = 21 lb = 15 rb = 15

la = 10 ra = 15 lb = 17 rb = 18

la = 15 ra = 15 lb = 17 rb = 17

la = 15 ra = 21 lb = 15 rb = 17

方法4:CPU 占用的总时间：10000000.000000 ns

中位数 16.000000

方法5:CPU 占用的总时间：0.000000 ns

中位数 16.000000

*/

⑸ 数据的算法都有哪些……

A*搜寻算法
俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的 NPC的移动计算，或线上游戏的 BOT的移动计算上。该算法像 Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

Beam Search
束搜索(beam search)方法是解决优化问题的一种启发式方法，它是在分枝定界方法基础上发展起来的，它使用启发式方法估计k个最好的路径，仅从这k个路径出发向下搜索，即每一层只有满意的结点会被保留，其它的结点则被永久抛弃，从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70年代中期首先被应用于 人工智能领域,1976 年Lowerre在其称为 HARPY的语音识别系统中第一次使用了束搜索方法。他的目标是并行地搜索几个潜在的最优决策路径以减少回溯，并快速地获得一个解。

二分取中查找算法
一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。

Branch and bound
分支定界算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

数据压缩
数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。

Diffie–Hellman密钥协商
Diffie–Hellman key exchange，简称“D–H”，是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。

Dijkstra’s 算法
迪科斯彻算法（Dijkstra）是由荷兰计算机科学家艾兹格·迪科斯彻发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离，迪科斯彻算法可以用来找到两个城市之间的最短路径。

动态规划
动态规划是一种在 数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。 动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。比较着名的应用实例有：求解最短路径问题，背包问题，项目管理，网络流优化等。这里也有一篇文章说得比较详细。

欧几里得算法
在 数学中，辗转相除法，又称 欧几里得算法，是求 最大公约数的算法。辗转相除法首次出现于 欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至 东汉出现的《九章算术》。

快速傅里叶变换(FFT)
快速傅里叶变换（Fast Fourier Transform，FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。

哈希函数
HashFunction是一种从任何一种数据中创建小的数字“指纹”的方法。该 函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列 函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

堆排序
Heapsort是指利用堆积树（堆）这种 数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父结点。

归并排序
Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

RANSAC 算法
RANSAC 是”RANdom SAmpleConsensus”的缩写。该算法是用于从一组观测数据中估计 数学模型参数的迭代方法，由Fischler and Bolles在1981提出，它是一种非确定性算法，因为它只能以一定的概率得到合理的结果，随着迭代次数的增加，这种概率是增加的。该算法的基本假设是观测数据集中存在”inliers”（那些对模型参数估计起到支持作用的点）和”outliers”（不符合模型的点），并且这组观测数据受到噪声影响。RANSAC 假设给定一组”inliers”数据就能够得到最优的符合这组点的模型。

RSA加密算法
这是一个公钥加密算法，也是世界上第一个适合用来做签名的算法。今天的RSA已经 专利失效，其被广泛地用于 电子商务加密，大家都相信，只要密钥足够长，这个算法就会是安全的。

并查集Union-find
并查集是一种树型的 数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

Viterbi algorithm
寻找最可能的隐藏状态序列
等等这些，算法很多。

⑹ 利用C语言定义有序数组，实现二分查找算法

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void xuanzhe(int a[], int n)
{
int i, j, min, t;

for (i=0; i<n-1; i++) /*要选择的次数：0~n-2共n-1次*/
{
min = i; /*假设当前下标为i的数最小，比较后再调整*/
for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/
{
if (a[j] < a[min])
{
min = j; /*如果后面的数比前面的小，则记下它的下标*/
}
}

if (min != i) /*如果min在循环中改变了，就需要交换数据*/
{
t = a[i];
a[i] = a[min];
a[min] = t;
}
}
}
int main(){
int i,n,x;
int mid,left=0,right=999;
int find1=0,find2=0;
double y;
int a[1000];
for(i=0;i<1000;++i){
a[i]=rand();
}
xuanzhe(a,1000);
scanf("%d",&x);
printf("顺序查找:\n");
for(i=0;i<1000;++i){
while(x==a[i]){
printf("找到X=%d,a[%d]\n",x,i);
find1=1;
break;
}
}
if(find1==0){
printf("没有你要找的数\n");
}

printf("%fs\n",clock()/CLOCKS_PER_SEC);
y=clock();
printf("二分查找:\n");
while(!find2&&left<right)
{
mid=(left+right)/2;
if(x==a[mid])
find2=1;
else if(x<a[mid])
right=mid-1;
else left=mid+1;
}
if(find2==1)
printf("找到x=%d ,a[%d]\n",x,mid);
else
printf("没有你要找的数\n");
printf("%fs\n",(clock()-y)/CLOCKS_PER_SEC);
}

⑺ 编写顺序查找算法的程序

查找算法集：顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)

// search.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "LinkTable.h"
#define MAX_KEY 500

//------------------------------数组实现部分----------------------------------
/**//*
无序数组顺序查找算法函数nsq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: nsq_Order_Search = -1
否则: nsq_Order_Search = key数组下标
*/
int nsq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = key;
/**//*for循环后面的分号必不可少*/
for(i=0;key!=array[i];i++);
return(i<n?i:-1);
}
/**//*
有序数组顺序查找算法函数sq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Order_Search = -1
否则: sq_Order_Search = key数组下标
*/
int sq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = MAX_KEY;
/**//*for循环后面的分号必不可少*/
for(i=0;key>array[i];i++);
if(i<n && array[i] == key)
return(i);
else
return(-1);
}
/**//*
有序数组二分查找算法函数sq_Dichotomy_Search0<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search0 = -1
否则: sq_Dichotomy_Search0 = key数组下标
*/
int sq_Dichotomy_Search0(int array[],int n,int key)
...{
int low,high,mid;
low = 0;
high = n - 1;

while(low<=high)
...{
mid = (high+low)/2;
if(array[mid] == key)
return(mid);
/**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/
/**//*否则,在[low,mid-1]*/
if(key > array[mid])
low = mid + 1;
else
high = mid - 1;
}
return(-1);
}
/**//*
有序数组插值查找算法函数sq_Dichotomy_Search1<用数组实现>
(插值查找算法是二分查找算法的改进)
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search1 = -1
否则: sq_Dichotomy_Search1 = key数组下标
*/
int sq_Dichotomy_Search1(int array[],int n,int key)
...{
int low,high, //二分数组的上,下标
pos; //查找码的大致(估算)位置
low = 0;
high = n-1;
while(low <= high)
...{
pos = (key-array[low])/(array[high]-array[low])*(high-low)+low;
/**//*找到关键值,中途退出*/
if(key == array[pos])
return(pos);
if(key > array[pos])
low = pos + 1;
else
high = pos - 1;
}
/**//*没有找到,返回-1*/
return(-1);
}
//------------------------------数组实现部分----------------------------------
//------------------------------链表实现部分----------------------------------
/**//*
无序链表顺序查找算法函数nlk_Order_Serach<用链表实现>
[查找思想:遍历链表的所有节点]
参数描述：
Node *head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: nlk_Order_Serach = NULL
否则: nlk_Order_Serach = 键值为key的节点的指针
*/
Node *nlk_Order_Serach(Node *head,int key)
...{
for(;head!=NULL && head->data != key;head = head->link);
return(head);
}
/**//*
有序链表顺序查找算法函数lk_Order_Serach<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node *head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: lk_Order_Serach = NULL
否则: lk_Order_Serach = 键值为key的节点的指针
*/
Node *lk_Order_Search(Node *head,int key)
...{
for(;head!=NULL && head->data < key;head=head->link);
/**//*当遍历指针为NULL或没有找到键值为key的节点,返回NULL(表明没有找到)*/
/**//*否则,返回head(表明已经找到)*/
return(head==NULL || head->data != key ? NULL : head);
}
/**//*
有序链表动态查找算法函数lk_Dynamic_Search<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node *head: 被查找链表的首指针
Node **p; 键值为key的节点的前驱指针(回传参数)
Node **q: 键值为key的节点指针(回传参数)
int key : 被查找的关键值
注意:
当 *p == NULL 且 *q != NULL,链表的首节点键值为key
当 *p != NULL 且 *q != NULL,链表的中间(非首,尾)节点键值为key
当 *p != NULL 且 *q == NULL,链表的尾节点键值为key
当 *p == NULL 且 *q == NULL,链表是空链表
*/
void lk_Dynamic_Search(Node *head,Node **p,Node **q,int key)
...{
Node *pre,*cur;
pre = NULL;
cur = head;
for(;cur != NULL && cur->data < key;pre = cur,cur = cur->link)
*p = pre;
*q = cur;
}
/**//*
有序链表动态插入算法函数lk_Dynamic_Insert<用链表实现>
参数描述：
Node *head: 被插入链表的首指针
int key : 被插入的关键值
返回值:
lk_Dynamic_Search = 插入键值为key的节点后的链表首指针
*/
Node *lk_Dynamic_Insert(Node *head,int key)
...{
Node
*x, //插入节点的前驱节点
*y, //插入节点的后续节点
*p; //插入的节点
p = (Node *)malloc(sizeof(Node));
p->data = key;
p->link = NULL;
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
...{
p->link = x;
head = p;
}
else
...{
p->link = x->link;
x->link = p;
}
ListLinkTable(head,"插入节点");
return(head);
}
/**//*
有序链表动态删除算法函数lk_Dynamic_Delete<用链表实现>
参数描述：
Node *head: 被删除链表的首指针
int key : 被删除的关键值
返回值:
lk_Dynamic_Delete = 删除键值为key的节点后的链表首指针
*/
Node *lk_Dynamic_Delete(Node *head,int key)
...{
Node *x, //删除节点的前驱节点
*y; //删除的节点
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
/**//*因为x=NLLL时,y指向首指针*/
head = y->link;
else
x->link = y->link;
free(y);
ListLinkTable(head,"删除节点");
return(head);
}
//------------------------------链表实现部分----------------------------------
int main(int argc, char* argv[])
...{
Node *head;
//Node *p,*x,*y;
int KEY;
int count,i;
//int result;
KEY = 11;
//PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始");
//result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY);
//printf("查找结果是：数组[%d] = %d ",result,TestArray2[result]);
head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2);
ListLinkTable(head,"原始");
/**//*
p = lk_Order_Search(head,KEY);
if(p==NULL)
printf(" 查找结果是：指定链表中没有[数据域 = %d]的节点! ",KEY);
else
printf(" 查找结果是：节点.Data = %d 节点.Link = %d 节点.Addr = %d ",p->data,p->link,p);
*/
printf("输入插入节点的个数： ");
scanf("%d",&count);
for(i=0;i<count;i++)
...{
printf("输入插入节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Insert(head,KEY);
}
do
...{
printf("输入删除节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Delete(head,KEY);
}while(head!=NULL);
printf(" 应用程序正在运行...... ");
return 0;
}

⑻ 数据结构算法查找，一个原本有序的数组，现随机取出前面一段放到后面去，然后再找到其中最小的数，详说

能用到的查找方法都是可以用的。顺序、建树、快速排序查找等等。
算法是很多，但对于本题来说，对于两段有序的表，从算法的时间复杂度来看，
还是用二分法（改良后）较好。就是最差的情况下，也不会比顺序查找长。

有二分法，找到一个中间的数值后，要进行两次比较，分为要和第一个元素、最后一个元素比较，才能确定下一次要二分的区间。
直到步长为1为止。

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

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

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

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

⑽ 二分搜索算法是利用什么实现的算法

二分搜索算法是利用排除剩余元素中一半的元素实现的算法。

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索算法原理：

1、如果待查序列为空，那么就返回－1，并退出算法；这表示查找不到目标元素。如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。如果不相等，就再比较这两个元素的大小。

2、如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。

3、如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。