C语言:折半寻找

C语言:折半搜索

//折半查找
#include <stdio.h>
int dichotomy(int m,int arr[],int left,int right)
{
 int mid;
 while(left <= right)
 {
  mid = left - (left - right)/2;
  if(m < mid)
   right = mid - 1;
  else if(m > mid)
   left = mid + 1;
  else
   return mid;
 }
 return -1;
}
int main()
{
 int a[] = {2,4,6,8,10,12,14,16,18};
 int search;
 int find;
 printf("请输入您要查找的数字:");
 scanf("%d", &search);
 find = dichotomy(search,a,0,8);
 if(find == -1)
  printf("NO find");
 else
  printf("您要找的数字为:%d\n",find);
 return 0;
}

 

http://www.bkjia.com/Cyy/1061008.htmlwww.bkjia.comtruehttp://www.bkjia.com/Cyy/1061008.htmlTechArticleC语言:折半查找 //折半搜寻#include stdio.hint
dichotomy(int m,int arr[],int left,int right){ int mid; while(left =
right) { mid = left – (left – right)/2; if(m mid) righ…

一、概念
二、代码
/*
 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图