二分法查找(折半查找)算法学习笔记

关键:数组中的元素必须是已经排好序的。

一维数组,二分法查找:

假如有一组数为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环境)

代码清单:

/******************************************************** 

************************半分法查找*********************** 

********************************************************/ 

#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++)<span style="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("Please input a integer:\n");            //提示用户输入要查找的值 

    scanf("%d", &n); 

    <span style="font-family: Arial, Helvetica, sans-serif;">//使用二分法进行查找</span> 

    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"); 

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/1c36230065528a02dd8c67d8929b2fd2.html