数据结构折半查找-排行榜大全

数据结构折半查找是折半查找技术，也就是二分查找。它的前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储。折半查找的基本思想是取中间记录作为比较对象，若给定值与中间记录的关键字，则在中间记录的关键字相等，则查找成功。若给定值小于中间记录的作伴去继续查找。若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

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

#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指向后半部分的第一个下标),然后仍然采取折半的方法,反复此操作直至找到该数的下标为止.

数据结构实验——折半查找

前子表查找：high=mid-1；
后子表查找：low=mid+1;
算法分析：
1.确定查找有序序列a,置查找区间初值，low为1，high为表长n。
2.当low小于等于high时，循环执行以下操作：
（1）mid取值为high和low的中间值；
（2）将查找值num与中间位置的关键字a[mid]进行比较，若相等则查找成功，输出查找值num在序列a中的位置mid；
（3）若查找值num小于中间位置a[mid],则进入前一子表中查找，high=mid-1;
（4）若查找值num大于中间位置a[mid],则进入后一子表中查找,low=mid+1;
3.循环结束，说明查找空间为空，则查找失败。
程序如下：

数据结构中的折半查找是怎么回事？谁能给个具体例子，谢谢了。

你好　：

这是我之前写的代码希望能对你有所帮助：

思路：

1.　务必是有序数组　（重点！）　

：（这里偷个懒）半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

这个代码输入为有序数组　，　寻找的值

返回：如果找到返回所在坐标，如果没找到返回最小的整型

/**
*
* @param arr 有序数组
* @param target 查找值
* @return   找到就返回坐标位置，找不到就返回最小值。
* @throws Exception
* @dec 二分查找的非递归算法，
* 时间复杂度： o log（n）   n  n/2  n/4  假设 k次找到。 n/(2的k次方) 即 2的k次方=n 所以k= logn
*
*/
public static int  binarySearch(int arr[], int target) throws Exception {
if(arr==null) {
throw new Exception("ARR IS NULL");
}
if(arr.length<=0) {
throw new Exception("length  is illegal");
}
int low = 0;
int high = arr.length-1;
while(low<=high) {
if(target==arr[(low+high)/2]) {
return (low+high)/2;
}else if(target>arr[(low+high)/2]) {
low = (low+high)/2 +1 ;
}else {
high = (low+high)/2 -1;
}
}
return Integer.MIN_VALUE;
}

如果有问题欢迎继续交流指教！