一萧锉、概念

二珊随、代碼

/*
 time.h
        clock_t 用于一個(gè)開啟一個(gè)時(shí)間
 折半查找的原理
 1.數(shù)組必須是有序的
 2.必須已知min和max(知道范圍)
 3.動(dòng)態(tài)計(jì)算mid的值,取出mid對(duì)應(yīng)的值 進(jìn)行比較
 4.如果mid對(duì)應(yīng)的值 大于了 需要查找的值, 那么max要變小 為 mid - 1
 5.如果mid對(duì)應(yīng)的值 小于了 需要查找的值, 那么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()
{
   // 現(xiàn)在已知一個(gè)有序的數(shù)組, 和一個(gè)key,要求從數(shù)組中找到key對(duì)應(yīng)的索引的位置
    
    // 對(duì)該方法進(jìn)行封裝,要求找到就返回對(duì)應(yīng)的索引,找不到就返回-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個(gè)一個(gè)對(duì)比
         一共要最少要比3次才能找到7
     
     如果找范圍小
        比如 key = 1 拿到中間值比 5 > 1
        那么max = 4 - mid - 1 
        此時(shí) max = 1  mid = (0+1) / 2 = 0
        此時(shí)取到 索引為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循環(huán) 一個(gè)一個(gè)查找
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;
    
    // 只要還在我們的范圍內(nèi)就需要查找
    while (min <= max) {
        // 計(jì)算中間值
        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; // 數(shù)組的最小值 = 0
    max = length -1; // 數(shù)組的最大值 等于長(zhǎng)度 -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;
        }
        
        // 超出范圍,數(shù)組中沒有需要查找的值
        if (min > max) {
            return -1;
        }
        // 每次改變完 min 和 max 都需要重新計(jì)算 mid
        mid = (min + max) / 2;
    }
//    printf("aa");

    return mid;
}