首页 / 操作系统 / Linux / 二分法查找（折半查找）算法学习笔记

关键：数组中的元素必须是已经排好序的。一维数组，二分法查找：假如有一组数为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环境）

代码清单:

1. /******************************************************** 
2. ************************半分法查找*********************** 
3. ********************************************************/ 
4. #define M 10 
5. #include <stdio.h> 
6. int main （void） 
7. { 
8.     int a[M]; 
9.     int n, low, mid, high, number;          /*变量n是让用户输入，变量low表示数组中的前位，mid表示数组中的中间位, 
10.                                             high表示数组中的后位，number用于表示查找是否成功*/ 
11.     int i, j, t;            //变量i，j用于对数组元素进行从大到小排序;变量t用于数组元素值的交换                         
12.  
13.              
14.     low = 0; 
15.     high = M-1; 
16.     number = 0; 
17.  
18.     printf（"Please input 10 numbers: "）; 
19.     for （n=0; n < 10; n++）           //使用循环让用户为数组元素赋值 
20.     { 
21.         printf（"a[%d]=", n）; 
22.         scanf（"%d", &a[n]）; 
23.     } 
24.      
25.     for （i=0; i < M-1; i++）<span style="white-space: pre;">          </span>//使用冒泡排序法进行从大到小的排序 
26.     { 
27.         for （j=0; j < M-1-i; j++） 
28.         { 
29.             if （a[j] < a[j+1]）           //a[j+1]代表数组元素的后一个元素 
30.             { 
31.                 t = a[j]; 
32.                 a[j] = a[j+1]; 
33.                 a[j+1] = t; 
34.             } 
35.         } 
36.     } 
37.     for （i=0; i < 10; i++）   
38.     { 
39.         printf（"%d ", a[i]）;           //输出排序后的数组元素 
40.     } 
41.     n = 0; 
42.     printf（"Please input a integer: "）;            //提示用户输入要查找的值 
43.     scanf（"%d", &n）; 
44.     <span style="font-family: Arial, Helvetica, sans-serif;">//使用二分法进行查找</span> 
45.     while （low <= high） 
46.     { 
47.         mid = （low+high）/2; 
48.         if （n == a[mid]） 
49.         { 
50.             number = 1; 
51.             break; 
52.         } 
53.         else if （a[mid] < n） 
54.         { 
55.             high = mid-1; 
56.         } 
57.         else 
58.         { 
59.             low = mid+1; 
60.         } 
61.     } 
62.     if （number == 1） 
63.     { 
64.         printf（"the index of %d is: %d ", n, mid）; 
65.     } 
66.     else 
67.     { 
68.         printf（"Program Can"t find the number！ "）; 
69.     } 

/********************************************************************************半分法查找*******************************************************************************/#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: "）;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 ", a[i]）;//输出排序后的数组元素}n = 0;printf（"Please input a integer: "）;//提示用户输入要查找的值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, mid）;}else{printf（"Program Can"t find the number！ "）;}
总结:折半查找算法是通过中间值（mid）与要查找的值（n）作比较,每一次比较都可以缩小其的查找范围;优点:比较次数少，查找速度快，平均性能好；缺点:要求待查表为有序表，且插入删除困难。本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-01/139680.htm