斐波拉契查找及二分查找

2024-06-20 09:18

文章标签 二分查找波拉

本文主要是介绍斐波拉契查找及二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

斐波拉契查找

代码

#include <stdio.h>
#include <stdlib.h>//求第n项的斐波拉契数
int fib(n) {int left = 0;int right = 1;while ( --n > 0 ) {right = left + right;left = right - left;} return right;
}//求n个斐波拉契数
int * fibList(n) {int *a = calloc(sizeof(int), n);for (int i = 0; i < n; i++) {a[i] = fib(i+1);}return a;
}int fibSearch(int *a, int size,int search) {int mid, low = 0, high = size-1;int *p = fibList(high-low);while(low < high) {int i = 0;while (high - low >= p[i]) { //查找符合的斐波拉契数i++;}mid = low + p[i-1] -1; //构造一个中点printf("low=%d,high=%d\n", low, high);printf("p[%d]=%d,mid=%d,a[mid]=%d\n", i-1, p[i-1], mid, a[mid]);if ( search < a[mid] ) {high = mid;} else if (a[mid] < search) {low = mid+1;} else {return mid;}}return -1;
}int main() {int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};printf("%d\n", fibSearch(a, 10, 7));
}

执行过程

low=0,high=9
p[5]=8,mid=7,a[mid]=8
low=0,high=7
p[4]=5,mid=4,a[mid]=5
low=5,high=7
p[2]=2,mid=6,a[mid]=7
6

二分查找

代码

int binSearch(int *a, int size, int search) {int mid, low = 0, high = size-1;while (low < high) {mid = (low + high) >> 1;if ( search < a[mid] ) {high = mid;} else if (a[mid] < search) {low = mid + 1;} else {return mid;}}return -1;
}