数据结构_查找_折半/插入/斐波那契

数据结构_查找_折半/插入/斐波那契

这三种查找算法都是在数据列有序的前提下进行的

折半查找

对于n个元素的数据列，顺序查找的时间规模就是n，折半查找的规模是n/2/.../2，...是m，其实就是2^m约等于n，也就是logn。

代码

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/halfSearch.png" width="400" />

注：有没有觉得我的背景很好看

插入查找

一本字典会按照首字母被分为多个部分供用户查找

看到折半查找的第9行了嘛，那里计算如何“折半”，那为什么不是折四分之一？

二分查找计算“一半”：mid = low+(high-low)/2

插入查找计算“多个折”：mid = low+(high-low)*(key-a[low])/(a[high]-a[low])

斐波那契查找

其实有序数列查找的这三个算法，核心都是怎么求的mid值，使算法更合理，斐波那契就是利用黄金分割来确定mid值

斐波那契原理：k=(k-1)+k(k-2)

斐波那契算法计算mid： mid=low+F[k-1]-1（F[k-1]-1就是那个中间位置）

原理：

1. 当key=a[mid]时，查找就成功
2. 当key<a[mid]时，新范围是第low个到第mid-1个，此时范围的个数为F[k-1]-1个
3. 当key>a[mid]时，新范围是第mid+1个到第high个，此时范围的个数为F[k-2]-1 个

'''

  \#include <stdio.h>

  int fibonacci(int arr[],int len,int key)
  {
      int fb[] = {0,1,1,2,3,5,8,13,21,34,55};
      int low=1,high=len,mid;
      int k = 0,i;
      //k第一次的位置
      while(fb[k]-1<len)
      {
          k++;
      }
      for(i=len;i<fb[k]-1;i++)
      {
          arr[i] = arr[len];
      }

      while(low<high)
      {
          mid = fb[k-1]-1;
          if(key<arr[mid])
          {
              high = mid-1;
              k = k-1;
          }
          else if(key>arr[mid])
          {
              low = mid+1;
              k = k-2;
          }else
          {
              if(mid<len)
              {
                   return mid;
              }else
              {
                  return len;
              }
          }

      }
      return 0;
  }

  int main(int argc,char *argv[])
  {
      int arr[] = {1,3,5,6,7,8,12,13,14,15};
      int key = 15;
      int len = sizeof(arr)/4;

      int result = fibonacci(arr,len,key);

      printf("%d\n",result);

      return 0;
  }

'''