A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© tingyuyisheng 中级黑马   /  2015-7-20 21:22  /  1390 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

dc5840b6-f468-4467-89f3-8f6c3defbd43
折半查找法:
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数num[0]~num[4],要查找的数是key,其基本思想是: 设查找数据的范围下限为low=0,上限为high=5,求中点mid=(low+high)/2,用key与中点元素a[mid]比较,若key==a[mid],即找到,停止查找;否则,若key>a[mid],替换下限low=mid+1,到下半段继续查找;若key<a[mid],换上限high=mid-1,到上半段继续查找;如此重复前面的过程直到找到或者low>high为止。如果low>high,说明没有此数,打印找不到信息,程序结束。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
定义一个折半查找法函数,查找一个数组元素无顺序的数组中的某个值的角标.
*/

#include <stdio.h>

/**
*  冒泡排序函数
*
*  @param arr 需要被排序的数组名
*  @param len 数组的长度
*/
void bubbleSort(int arr[],int len){
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1 - i; j++) {
            if (arr[j]>arr[j+1]) {
                arr[j] = arr[j] ^ arr[j+1];
                arr[j+1] = arr[j] ^ arr[j+1];
                arr[j] = arr[j] ^ arr[j+1];
            }
        }
    }
}

/**
*  折半查找函数
*
*  @param arr 要被查找的数组名
*  @param len 要呗查找的数组的长度
*  @param key 要查找的值
*
*  @return 如果查到则返回角标,查不到返回-1
*/
int Czhao(int arr[],int len,int key){
    //定义三个变量,low表示最小角标,high表示最大角标,mid假设为要查找的数的角标
    int low = 0,high = len -1,mid;

    while (low<=high) {

        //计算mid的值,也就是计算角标
        mid = (low + high)/2;

        //判断key和arr[mid]的值
        if (key > arr[mid]) {
            //当要查的值大于中间值,说明要查的值在中间值和最大值之间,则最小角标等于中间角标+1后继续计算新的mid值
            low = mid + 1;
        }else if(key < arr[mid]){
            //当要查的值小于中间值,说明要查的值在最小值和中间值之间,则最大角标等于中间角标-1后继续计算新的mid值
            high = mid - 1;
        }else{
            //当要查的值等于中间值,则直接返回角标
            return mid;
        }
    }
    //查找不到,返回-1
    return -1;
}

int main(int argc, const char * argv[]) {

    //定义一个长度为5的int类型的数组,并赋值
    int num[5] = {3,1,5,7,5};

    //调用冒泡排序函数,对数组进行排序
    bubbleSort(num, 5);

    //调用折半查找函数,并将返回值赋值给n
    int n = Czhao(num, 5, 5);

    //打印角标
    printf("要查找的元素的角标为:%d\n",n);
    return 0;
}

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马