现在有一个任务:从一堆有序数字中找出其中一个数字
有两种方法
1)从头到尾依次寻找
2)从该些数字中中间部位比较若小于要找数字则在后半部分否则在前半部分
再进行这样的方式进行循环,直至找到或找不到此数字
现介绍这样的方法——二分法
在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
现在剖析算法
首先定义一个包含n个数字的数组A中有A0
(1)令L=0,R=n-1
(2)如果L>R则截止
(3)m=(L+R)/2
(4)Am
(5)Am&g服务器托管网t;T 则R=m-1 并返回(2)
(6)Am=T时搜索结束,返回m
从分析可以看出可以用循环,也可以用递归
此次用循环的方法写一次
#include
int main()
{
int arr[]={0,1,2,3,4,5,6,7,8,9,12,13,22,55,66,77,78,79,80,87,88,89,90,99,100};
int left=0;
int sz=sizeof(arr)/sizeof(arr[0]);
int right=sz-1;
int k=0;
scanf("%d",&k);
while(leftk)
{
right=mid-1;
}
else if(arr[mid]r服务器托管网ight)
{
printf("找不到");
}
return 0;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
随着系统的上线,我们不出意外地获服务器托管网得了成功。市场上出现了一批忠实于我们的用户,使得系统的访问量逐步上升,逐渐逼近了硬件资源的极限,同时团队也在此期 间积累了对业务流程的一批经验。面对当前的性能压力,我们需要未雨绸缪去进行系 统重构、架构挑战,以提升系…