admin 管理员组

文章数量: 1087817

c++实现二分法查找

二分查找也属于顺序表查找范围，二分查找也称为折半查找。二分查找(有序)的时间复杂度为O(LogN)。

那么什么是二分查找呢？二分查找的基本思想是， 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到找到为止。

从二分查找的定义我们可以看出，使用二分查找有两个前提条件：

1，待查找的列表必须有序，这里使用递归快排来使产生的随机无序数组有序。

2，必须使用线性表的顺序存储结构来存储数据。

下面是c++实现代码。

//用递归快速排序对随机产生的一组无序数组进行排序，再查找给定的数字，并返回下标，2016.5.27
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#define  MAX 101
void input(int num[])//实参传入的数组的首地址，而不是整个数组
{int i;srand((unsigned)time(NULL));//产生随机函数的随机数种子for (i = 1; i < MAX; i++){num[i]=rand() % 100;}
}void  output(int num[])
{int i;for (i = 1; i <= MAX; i++){printf("%5d", num[i]);if (i % 10 == 0)printf("\n");}}int Partition( int num[], int low, int high)
{//int pivotkey;//这个枢轴的选取很关键，改进版的可以用三数取中，就九数取中等int pivotkey=num[low];//在这里就取第一个元素num[0] = pivotkey;//备份到num【0】，while (low < high){while (low < high&&num[high] >= pivotkey)high--;num[low] = num[high];//不满足循环条件就执行这个语句while (low < high&&num[low] <= pivotkey)low++;num[high] = num[low];//交换low，是因为low=pivotkey,比较了。}num[low] = num[0];return low;//最后high和low在某一个位置相遇，就是切分部的值。
}void Qsort(int num[], int low, int high)//对随机产生的无序数组进行快速排序，这也是二分法的缺陷之一。
{//快排对很多数据更有优势，可以设置一个数据个数的阈值，才进行快排，这里也是一个优化的地方int pivot;//if (low < high){pivot = Partition(num, low, high);Qsort(num, low, pivot - 1);//递归的深度决定了时间的复杂度。Qsort(num, pivot + 1, high);}
}int binaryfind(int num[], int x, int low, int high)
{while (low <=high){int mid=(low + high) / 2;if (x <=num[mid])high=mid - 1;else if (x >= num[mid])low=mid + 1;elsereturn mid;}
}void main()
{int x, pos, num[MAX];time_t start, end;time(&start);input(num);printf("排序前：\n");output(num);Qsort(num, 0, MAX - 1);printf("排序后：\n");output(num);printf("请输入要查找的数字：");scanf("%d", &x);pos = binaryfind(num, x, 0, MAX - 1);if (pos)printf("OK!,%d is find in pos %d\n", x, pos);elseprintf("sorry!,%d is not find ......\n", x);time(&end);printf("已运行%d秒\n", end-start);system("pause");
}


本文标签： c实现二分法查找

版权声明：本文标题：c++实现二分法查找 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700276601a376082.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。