一、问题描述:
二、设计思路:
折半查找思路是找首位置low,和末位置high,中间位置mid=(首位置+末位置)/2,满足的循环是首位置<=末位置,如果中间的位置上的数小于要找的目标,则low=mid+1转换为新的首位置和末位置之间找数字,之间缩小一半的范围,这就是二分查找的妙处,如果中间的位置上的数大于要找的目标,则high=mid-1。老在理论上说也不好理解,咱们能动手就不动口,看图
三、程序流程图:
四、代码实现
#include<stdio.h> #include<math.h> #define N 11 int main() { int a[N]={5,13,19,21,37,56,64,75,80,88,92}; int target; int lenth=sizeof(a)/sizeof(a[0]); int index=-1; int low=0,mid,high=lenth-1; scanf("%d",&target); while(low<=high) { mid=(high+low)/2; if(a[mid]==target) { index=mid; break; } else if(a[mid]<target) { low=mid+1; } else high=mid-1; } if(index==-1) { printf("Not be found"); } else printf("%d找到了下标为:%d",target,index); return 0; }
值得注意的是我们弄了一个单独的变量index并赋了初值-1,这个就是我们拿来记录下标的,这里用到了一个计算数组长度的方法,lenth=sizeof(a)/sizeof(a[0])。回忆一下,昨天学的冒泡排序在折半查找中也能用上,折半查找要求必须是一个有序的数组,要么是升序,要么是降序,冒泡加折半查找就能解决我们大部分问题了
标签:折半,int,查找,lenth,low,sizeof From: https://www.cnblogs.com/bzsc/p/17338328.html