数组查找算法
1. 查找算法：采用二分法在有序数组 中查找一数，指出数的位置和查找次数。
#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;
}
2. 如何用二分查找法查找一个数组中的元素
二分查找又叫折半查找，但是有一个前提条件，就是你要查找的数据必须是按顺序储存，以关键字大小来排列的。
例如
如果是整形数组，存放0~9这10个数，数组必须按0到9（升序）或者9到0（降序）挨个储存。
如果你数组的元素之字符串，字符串的首字母就得按a~z或者z~a挨个储存，当最高位相同时比较次高位。
当你保证数组有序后，就可以开始执行二分查找了。
举个例子
1,3,6,8,9,10,11,15
如果你要查找的数字是10，查找过程如下
由于一共有7个元素，比较最中间的元素，即第四个，10>9，由于是升序排列，选择9的右边三个数进行比较,，这就将比较次数缩短了一半。在右半部分再去中间元素，即11,10<11，选取11左边部分进行比较，即和10进行比较，得到要找的元素。
当然也存在找不到的情况，比如找12，先与9比，范围缩小至右半部分，跟11比，在此基础上再缩小至现有右半部分，只剩一个15，不相等， 即没找到想要的元素。
这就是一个递归缩小范围的过程
3. 利用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);
}
4. 如何实现无序数组的快速查找
如果只是查找单个数字没有优化算法，只能是遍历所有数字，与指定数字比较，相等则退出，复杂度O（n）;
如果要查找k个指定数字则可以首先将k个数字排序去重，然后采用不同算法：
1）遍历所有无序数字，对每个数字用二分查找法到k个数字中搜索是否存在，如存在则表示无序数字中有该数字，否则则没有，复杂度O(nlogk)。
2）用第k/2个指定数字将原无序数字拆分成两半----类似与快排的算法，这样就知道第k/2个指定数字是否存在了，然后分别用第k/4和3k/4个指定数字拆分第一次拆分出来的两半无序数组，然后依次进行， 复杂度也为O(nlogk)。
PXE BIS Policy/PXE BIS Default Policy
5. 思考:在含有n个元素的一维数组中顺序查找一个。值k的数组元素的算法: ”考虑此算法的时间复杂度。
这个搜索算法的代码写错了。圆括号的参数表中，第一个参数应该是一个指针参数int *a。还有， 循环部分应该是for(i=0;i<n;i++)，整体应该是：
int search(int *a int n, int k)
{
for(i=0; i<n; i++ )
if(a[i]==k) return i;
return -1;
}
整个查找算法的时间复杂度是O(n)。
6. 一个无序的数组，有什么高效的查找算法
无序的序列，如果只进行极少量的查找，最快也是最简单的算法是从顺序地扫描查找；
如果是大量地查找，先用快排排序，再用二分查找 ！
7. 数组的冒泡排序和分块查找法
#include<iostream.h>
const int N=12,M=3;
void numbers (int a[]) //输入数组元素
{
cout<<"请输入"<<N<<"个元素"<<endl;
for(int i=0;i<N;i++)
cin>>a;
}
void sort(int a[],int n) //冒泡法排序
{
int t;
for(int i=0;i<n-1;i++)
for(int j=0;j<n-1-i;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
void search(int a[]) //分块查找法
{
int x,j,i;
cout<<"请输入要查找的元素"<<endl;
cin>>x;
int b[N][2];
for(j=0,i=3;j<3,i<12;j++,i+=4)
b[j][0]=a;
for(j=0,i=0;j<3,i<12;j++,i+=4)
b[j][1]=i;
for(j=0;j<3;j++)
{
if(x<=b[j][0])
break;
}
if(x>a[N-1])
{
cout<<x<<" "<<"不在您要查找的数组中"<<endl;
return;
}
{
int top=b[j][1],bottom=b[j][1]+N/M-1,middle=(top+bottom)/2; //折半查找法
while(top<=bottom)
{
if(x==a[middle])
break;
else if(x>a[middle])
top=middle+1;
else
bottom=middle-1;
middle=(top+bottom)/2;
}
if(x==a[middle])
{
cout<<x<<" "<<"在您要查找的数组中"<<endl;
}
else
{
cout<<x<<" "<<"不在您要查找的数组中"<<endl;
}
}
}
8. 用递归方法写出有序数组的二分查找算法
什么是二分查找？
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找优缺点
优点是比较次数少，查找速度快，平均性能好；
其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。
过程
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
利用循环的方式实现二分法查找
public class BinarySearch {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));
System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一个随机数组 *
* @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---循环的方式实现 *
* @param array 要查找的数组 * @param aim 要查找的值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim) {
// 数组最小索引值 int left = 0;
// 数组最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围 if (aim < array[mid]) {
right = mid - 1;
// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找数据与中间元素值正好相等，则放回中间元素值的索引 } else {
return mid;
}
}
return -1;
}}
运行结果演示：
总结：
递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~
9. 为什么要用到数组及遍历数组和数组里数据的查找方法
查找的意义是在一堆数据中，使用方法找到你想要找的数据。
一般为分：顺序和折半（又叫二分）查找两种方法。
存放在数组中的数据就可以看成一堆数据，在有限数组内存放一些数据，通过使用查找方法进行查找想要找的数。
顺序方法：这种查找方法不需要数组排序，数据可以是无序的。从数组开头向后一个一个与被查找数进行比较，如果找到就做相应的操作（如输出这个数的下标或位置）等。
折半查找法：（二分查找）
前提需要把数组里的数据进行排序（升序或降序）。思路是（假设数组已按升序排序）每次只比较中间的数据（一段距离内），第一次先和中间的数组（下标是这个数组中在中间的）比较，如果相同，则说明被找数已找到。否则就要判断是在大于还是小于：如果是大于，那么就将在中间+1至最后一个数之间的中间数再进行比较。否则就将在第一个至中间-1的数进行比较；再次重复比较，直到找到数为止。
10. 一个无序的数组，有什么高效率的查找算法
无序数组只有依次查找，如果需要查找的次数很多，可以先排序，如果需要查找的次数很多很多，而且是按固定的条件进行查询，那可以考虑建立HASH映射。