/*
二分搜寻法(搜寻原则的代表)
说明如果搜寻的数列已经有排序,应该尽量利用它们已排序的特性,以减少搜寻比对的次数,
这是搜寻的基本原则,二分搜寻法是这个基本原则的代表。
解法在二分搜寻法中,从数列的中间开始搜寻,如果这个数小于我们所搜寻的数,由于数列
已排序,则该数左边的数一定都小于要搜寻的对象,所以无需浪费时间在左边的数;如果搜寻
的数大于所搜寻的对象,则右边的数无需再搜寻,直接搜寻左边的数。
所以在二分搜寻法中,将数列不断的分为两个部份,每次从分割的部份中取中间数比对,例如
要搜寻92于以下的数列,首先中间数索引为(0+9)/2 = 4(索引由0开始):
[3 24 57 57 67 68 83 90 92 95]
由于67小于92,所以转搜寻右边的数列:
3 24 57 57 67 [68 83 90 92 95]
由于90小于92,再搜寻右边的数列,这次就找到所要的数了:
3 24 57 57 67 68 83 90 [92 95]
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void quicksort(int[], int, int);
int bisearch(int[], int);
int main(void) {
int number[MAX] = {0};
int i, find;
srand(time(NULL));
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
}
quicksort(number, 0, MAX-1);
printf("数列:");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n输入寻找对象:");
scanf("%d", &find);
if((i = bisearch(number, find)) >= 0)
printf("找到数字于索引%d ", i);
else
printf("\n找不到指定数");
printf("\n");
return 0;
}
int bisearch(int number[], int find) {
int low, mid, upper;
low = 0;
upper = MAX - 1;
while(low <= upper) {
mid = (low+upper) / 2;
if(number[mid] < find)
low = mid+1;
else if(number[mid] > find)
upper = mid - 1;
else
return mid;
}
return -1;
}
void quicksort(int number[], int left, int right) {
int i, j, k, s;
if(left < right) {
s = number[(left+right)/2];
i = left - 1;
j = right + 1;
while(1) {
while(number[++i] < s) ; // 向右找
while(number[--j] > s) ; // 向左找
if(i >= j)
break;
SWAP(number[i], number[j]);
}
quicksort(number, left, i-1); // 对左边进行递回
quicksort(number, j+1, right); // 对右边进行递回
}
}
没有合适的资源?快使用搜索试试~ 我知道了~
二分搜寻法.zip
共1个文件
c:1个
0 下载量 76 浏览量
2024-04-24
22:45:39
上传
评论
收藏 2KB ZIP 举报
温馨提示
算法是解决特定问题或执行特定任务的一系列步骤或规则的有序集合。在计算机科学中,算法通常用来指导计算机执行特定的任务或解决问题。良好设计的算法能够有效地解决问题,并且在给定的输入下能够产生正确的输出。 常见的算法包括但不限于以下几种: 排序算法:排序算法是将一组数据按照一定的顺序排列的算法。常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。 搜索算法:搜索算法用于在数据集中查找特定元素的算法。常见的搜索算法包括线性搜索、二分搜索等。 图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂问题的算法。常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符串匹配算法:字符串匹配算法用于在一个字符串(文本)中查找一个子串(模式)的出现位置。常见的字符串匹配算法包括暴力匹配、KMP算法、Boyer-Moore算法等。 这些是计算机科学中常见的算法类型,每种算法都有不同的应用场景和解决问题的方法。在实际编程中,选择合适的算法对于提高程序效率和性能至关重要。
资源推荐
资源详情
资源评论
收起资源包目录
二分搜寻法.zip (1个子文件)
二分搜寻法
二分搜寻法.c 3KB
共 1 条
- 1
资源评论
枫蜜柚子茶
- 粉丝: 6161
- 资源: 4168
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功