数据结构折半查找算法的方法

发布网友 发布时间：2022-04-21 03:19

我来回答

共3个回答

热心网友 时间：2022-04-27 00:19

#include <stdio.h>

int Dichotomy(int a[],int _value,int n){ // 二分法(也称折半查找法)
   int index=0; // 当前数组的首元素下标
   int current=n-1; // 数组当前的大小
   int k;  // 当前数组中间的数的下标
   
   while (index<current)
   {
       // 开始二分法查找
       k=(index+current)/2; // 除以2代表得到当前数组中间的数的下标
   if(a[k]==_value) return k; // 返回要查找的值_value所在的下标

   // 否则比较要查找的值_value是在折半后的前半部分还是后半部分
   if(a[k]<_value){ // 说明要查找的值在折半后的后半部分
           index=k+1; // 令index指向后半部分数组的首元素
   }
   else{  // 说明要查找的值在折半后的前半部分
          current=k-1; // 令current等于前半部分数组的长度
   }

   }
   return -1; // 返回-1代表没有查找到该值(_value)
}
void main(){
    int arr[5]={2,12,45,87,95};// 前提是一组数组必须是有序数对(即按小到大或大到小)

    if(Dichotomy(arr,87,5)!=-1) 
printf("87在数组中对应的下标是:%d\n",Dichotomy(arr,87,5));
    else printf("没有找到指定的值\n");
}
// 用一句话概括二分法(折半查找法)的思想就是:在一组有序对数组中反复折半后得到中间数组的下标,然后再进行是否与要查找的值相等,若相等则返回当前要查找的值的下标。

那么，上面的代码的注释与下面一一对应，它在执行的结果会产生两种情况，第一种,不存在。第二种，存在。
先来说说第一种情况 不存在：
 1.如果给定要查找的值_value大于数组中最大的数,则index不断增大从而促使while循环终止 2.如果给定要查找的值_value小于数组中最小的数,则current不断减少从而促使while循环终止(你自己可以动手在纸上画一个数组,然后思路跟着代码走就会知道或设单步调试亦可)
 
 第二种情况 存在：
 1.要查找的数_value正好是在数组中间.那么就执行了一次循环,当然这也是最理想的效果.

否则反复执行2和3:
2.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果小于中间的数则说明_value应该在数组中间的前半部分,那么current=k-1(即令current等于前半部分的长度),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.

3.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果大于中间的数则说明_value应该在数组中间的后半部分,那么index=k+1(即令index指向后半部分的第一个下标),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.

热心网友 时间：2022-04-27 01:37

12345671011121314151617181920212223242526272829303132333435363738394041424344#include <stdio.h> int Dichotomy(int a[],int _value,int n){ // 二分法(也称折半查找法) int index=0; // 当前数组的首元素下标 int current=n-1; // 数组当前的大小 int k; // 当前数组中间的数的下标 while (index<current) { // 开始二分法查找 k=(index+current)/2; // 除以2代表得到当前数组中间的数的下标 if(a[k]==_value) return k; // 返回要查找的值_value所在的下标 // 否则比较要查找的值_value是在折半后的前半部分还是后半部分 if(a[k]<_value){ // 说明要查找的值在折半后的后半部分 index=k+1; // 令index指向后半部分数组的首元素 } else{ // 说明要查找的值在折半后的前半部分 current=k-1; // 令current等于前半部分数组的长度 } } return -1; // 返回-1代表没有查找到该值(_value)}void main(){ int arr[5]={2,12,45,87,95};// 前提是一组数组必须是有序数对(即按小到大或大到小) if(Dichotomy(arr,87,5)!=-1) printf("87在数组中对应的下标是:%d\n",Dichotomy(arr,87,5)); else printf("没有找到指定的值\n");}// 用一句话概括二分法(折半查找法)的思想就是:在一组有序对数组中反复折半后得到中间数组的下标,然后再进行是否与要查找的值相等,若相等则返回当前要查找的值的下标。 那么，上面的代码的注释与下面一一对应，它在执行的结果会产生两种情况，第一种,不存在。第二种，存在。先来说说第一种情况 不存在： 1.如果给定要查找的值_value大于数组中最大的数,则index不断增大从而促使while循环终止 2.如果给定要查找的值_value小于数组中最小的数,则current不断减少从而促使while循环终止(你自己可以动手在纸上画一个数组,然后思路跟着代码走就会知道或设单步调试亦可) 第二种情况 存在： 1.要查找的数_value正好是在数组中间.那么就执行了一次循环,当然这也是最理想的效果. 否则反复执行2和3:2.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果小于中间的数则说明_value应该在数组中间的前半部分,那么current=k-1(即令current等于前半部分的长度),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止. 3.如果要查找的数_value不存在中间,则判断它是否大于中间的数还是小于中间的数,如果大于中间的数则说明_value应该在数组中间的后半部分,那么index=k+1(即令index指向后半部分的第一个下标),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.

热心网友 时间：2022-04-27 03:11

折半查找适合顺序表的查找，数组中存的是按顺序排列的元素，方法如下：

定义变量low，mid，high分别指向数组中的最低位，中间和最高位的元素；

比较要查找的元素和mid指向的元素，如果比mid大，则在mid和high之间继续查找,low=mid+1;否则在low和mid之间继续查找，high=mid-1。

直到low大于high停止，找到要找的元素则返回标号，未找到则返回null。

实际上就是比较一次能排除一半的元素，再在另一半的元素里查找，直到找到或者失败。