关键:数组中的元素必须是已经排好序的。
一维数组,二分法查找:
假如有一组数为1,2,3,4, 5 ,6,7, 8, 9, 10要查给定的值7.可设三个变量low,mid,high分别指向数据的前,中间和后,mid=(low+high)/2.思路:1:将low=0,值为1;high=9,值为10(因为数组下标从0开始);mid=(low+high)/2,即等于4,值为32(因为整型会省略小数点);2:将mid的值与查找的数作比较,如果mid<n(这里假设要查找的数为n),说明n在mid的后边,则使得low=mid+1,high不变;如果n<mid,说明n在mid的前边,则使得high=mid-1,low不变;如果mid==n,你懂的...3:现在的mid等于4,值为5,查找的范围为:5,6,7,8,9,10,显然mid<n,此时mid执行2次循环便等于7,然后输出mid.
例如: 设计一个程序,提供用户输入10个整数并保存到数组中,将整数以从大到小的顺序排列,最后通过半分法查找用户输入的值并显示值的序号.(VC++6.0环境)
代码清单:
- /******************************************************** ************************半分法查找***********************
- ********************************************************/ #defineM10
- #include<stdio.h> intmain(void)
- { inta[M];
- intn,low,mid,high,number; /*变量n是让用户输入,变量low表示数组中的前位,mid表示数组中的中间位, high表示数组中的后位,number用于表示查找是否成功*/
- inti,j,t; //变量i,j用于对数组元素进行从大到小排序;变量t用于数组元素值的交换
- low=0;
- high=M-1; number=0;
- printf("Pleaseinput10numbers:\n");
- for(n=0;n<10;n++) //使用循环让用户为数组元素赋值 {
- printf("a[%d]=",n); scanf("%d",&a[n]);
- }
- for(i=0;i<M-1;i++)<spanstyle="white-space:pre;"> </span>//使用冒泡排序法进行从大到小的排序 {
- for(j=0;j<M-1-i;j++) {
- if(a[j]<a[j+1]) //a[j+1]代表数组元素的后一个元素 {
- t=a[j]; a[j]=a[j+1];
- a[j+1]=t; }
- } }
- for(i=0;i<10;i++) {
- printf("%d\t",a[i]); //输出排序后的数组元素 }
- n=0; printf("Pleaseinputainteger:\n"); //提示用户输入要查找的值
- scanf("%d",&n); <spanstyle="font-family:Arial,Helvetica,sans-serif;">//使用二分法进行查找</span>
- while(low<=high) {
- mid=(low+high)/2; if(n==a[mid])
- { number=1;
- break; }
- elseif(a[mid]<n) {
- high=mid-1; }
- else {
- low=mid+1; }
- } if(number==1)
- { printf("theindexof%dis:%d\n",n,mid);
- } else
- { printf("ProgramCan'tfindthenumber!\n");
- }
/********************************************************************************半分法查找*******************************************************************************/#define M 10#include <stdio.h>int main (void){int a[M];int n, low, mid, high, number;/*变量n是让用户输入,变量low表示数组中的前位,mid表示数组中的中间位,high表示数组中的后位,number用于表示查找是否成功*/int i, j, t;//变量i,j用于对数组元素进行从大到小排序;变量t用于数组元素值的交换low = 0;high = M-1;number = 0;printf("Please input 10 numbers:\n");for (n=0; n < 10; n++)//使用循环让用户为数组元素赋值{printf("a[%d]=", n);scanf("%d", &a[n]);}for (i=0; i < M-1; i++)//使用冒泡排序法进行从大到小的排序{for (j=0; j < M-1-i; j++){if (a[j] < a[j+1])//a[j+1]代表数组元素的后一个元素{t = a[j];a[j] = a[j+1];a[j+1] = t;}}}for (i=0; i < 10; i++) {printf("%d\t", a[i]);//输出排序后的数组元素}n = 0;printf("Please input a integer:\n");//提示用户输入要查找的值scanf("%d", &n);//使用二分法进行查找while (low <= high){mid = (low+high)/2;if (n == a[mid]){number = 1;break;}else if (a[mid] < n){high = mid-1;}else{low = mid+1;}}if (number == 1){printf("the index of %d is: %d\n", n, mid);}else{printf("Program Can't find the number!\n");}
总结:折半查找算法是通过中间值(mid)与要查找的值(n)作比较,每一次比较都可以缩小其的查找范围;
优点:比较次数少,查找速度快,平均性能好;
缺点:要求待查表为有序表,且插入删除困难。
本文永久更新链接地址:http://www.xuebuyuan.com/Linux/2017-01/139680.htm
以上就上有关二分法查找(折半查找)算法学习笔记的相关介绍,要了解更多二分法查找法,二分法查找(折半查找)算法学习笔记,编程,Linux编程,Linux Shell,Android,Android教程,JAVA,C语言,Python,HTML5内容请登录学步园。