第07天C语言(13):折半查找

一、概念

二、代码

/*
 time.h
        clock_t 用于一个开启一个时间
 折半查找的原理
 1.数组必须是有序的
 2.必须已知min和max(知道范围)
 3.动态计算mid的值,取出mid对应的值 进行比较
 4.如果mid对应的值 大于了 需要查找的值, 那么max要变小 为 mid - 1
 5.如果mid对应的值 小于了 需要查找的值, 那么mix要变大 为 mid + 1
 */
#pragma mark 代码
#include <stdio.h>
#include <time.h>
int findKey2(int nums[],int length,int key);
int findKey3(int nums[],int length,int key);
int main()
{
   // 现在已知一个有序的数组, 和一个key,要求从数组中找到key对应的索引的位置
    
    // 对该方法进行封装,要求找到就返回对应的索引,找不到就返回-1
    int nums[50000]  = {1,3,5,7,9,[49999]=66};
    
    /*

     最小索引 min = 0
     最大索引 max = 4
     中间索引 mid = (min + max) / 2
     找范围大的
        比如 key = 7 拿到mid的中间值 5 < 7
        那么min  = mid + 1  = 2 + 1
         (3 + 4) / 2 = 3
         7 = 7 则比较匹配
         这里只匹配了2次
         之前都是1个一个对比
         一共要最少要比3次才能找到7
     
     如果找范围小
        比如 key = 1 拿到中间值比 5 > 1
        那么max = 4 - mid - 1 
        此时 max = 1  mid = (0+1) / 2 = 0
        此时取到 索引为0 则 1 = 1
     
     
     
     */
    int key = 66;
    int length = sizeof(nums)/sizeof(nums[0]);
    
    /*
    for (int i = 0; i < length; i++) {
        if (nums[i] == key) {
            printf("%i\n",i);
        }
    }
     */
    
    /*
    clock_t startTime = clock();
    int index = findKey(nums, key, length);
    clock_t endTime = clock();
    printf("消耗了多少%lu毫秒\n",endTime -startTime );
    printf("index = %i\n",index);
    */
    clock_t startTime = clock();
//    int indexs = findKey2(nums, length, key);
    int indexs = findKey3(nums, length, key);

    clock_t endTime = clock();
    printf("消耗了多少%lu毫秒\n",endTime -startTime );
    printf("index = %i\n",indexs);
    
    return 0;
}
#pragma 1.for循环 一个一个查找
int findKey(int nums[],int key,int length)
{
    for (int i = 0; i < length; i++) {
        if (nums[i] == key) {
//            printf("%i\n",i);
            return i;
        }
    }
    return  -1;
}

#pragma 2.折半查找
int findKey3(int nums[],int length,int key)
{
    int min,max,mid;
    min = 0;
    max = length - 1;
    
    // 只要还在我们的范围内就需要查找
    while (min <= max) {
        // 计算中间值
        mid = (min + max) / 2;
        
        if (key > nums[mid]) {
            min = mid + 1;
        }
        else if (key < nums[mid])
        {
            max = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

int findKey2(int nums[],int length,int key)
{
    int min ,max,mid;
    min = 0; // 数组的最小值 = 0
    max = length -1; // 数组的最大值 等于长度 -1
    mid = (min + max) / 2; // 中间值
    /*

     如果查找的值 > mid的值 那么 min要变大 min = mid + 1
     如果查找的值 < mid的值 那么 max要变小 max = mid - 1
     */
    
    while (key != nums[mid]) {
        // 断如果 查找的值 大于 取出的值, min 要变改
        if (key > nums[mid]) {
            min = mid + 1;
        }
        // 判断如果 要找的值 小于 取出的值, max 要改变
        else if (key < nums[mid])
        {
            max = mid - 1;
        }
        
        // 超出范围,数组中没有需要查找的值
        if (min > max) {
            return -1;
        }
        // 每次改变完 min 和 max 都需要重新计算 mid
        mid = (min + max) / 2;
    }
//    printf("aa");

    return mid;
}