一、二分查找
在C和C++里,二分查找是针对有序数组所用的一种快速查找元素的方法。
二、二分查找的条件以及优缺点
条件:针对有序数组(元素从小到大或从大到小)
优点:查询速度较快,时间复杂度为O(n)
缺点:有硬性条件的限制,而且即使查到后,插入与删除困难。
三、图片详解
四、代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 15
int main()
{
int i, number, top, bott, mid, loca, a[N], flag = 1, sign;
char c;
printf("enter data n");
scanf("%d", &a[0]);
i = 1;
while (i<N)
{
scanf("%d", &a[i]);
if (a[i]>=a[i-1])
{
i++;
}
else
{
printf("enter this data again: n");
}
}
printf("n ");
for (i = 0; i < N; i++)
{
printf("%5d", a[i]);
}
printf("n ");
while (flag)
{
printf("input number to look for:");
scanf("%d", &number);
sign = 0;
top = 0;//top 是查找区间的其实位置
bott = N - 1;//bott是查找区间的最末位置
if ((number<a[0])||(number>a[N-1]))//要查找的数不在查找区间
{
loca = -1;//表示找不到
}
while ((!sign)&&(top<bott))
{
mid = (top + bott) / 2;
if (number==a[mid])
{
loca = mid;
printf("Has found %d,its position is %d n", number, loca + 1);
sign = 1;
}
else if (number < a[mid])
{
bott = mid - 1;
}
else
{
top = mid + 1;
}
}
if (!sign||loca==-1)
{
printf("can not find %d. n", number);
}
printf("continue or not?(Y/N)");
scanf("%c", &c);
if (c=='N'||c=='n')
{
flag = 0;
}
}
}
原文链接: https://www.cnblogs.com/qixinbo/p/7685478.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/261464
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!