织梦可以仿所有网站吗,电子商务网站建设臧良运课后答案,百度一下你就知道移动官网,网站返回顶部怎么做二分查找#xff1a;
获取查找区域的中间位置。若中间位置的数据就是要找的值#xff0c;则返回true。若要找的值 小于 中间位置的数据#xff0c;则往左边查找。若要找的值 大于 中间位置的数据#xff0c;则往右边查找。重复1和2#xff0c;若没有要找的值#xff0c;…二分查找
获取查找区域的中间位置。若中间位置的数据就是要找的值则返回true。若要找的值 小于 中间位置的数据则往左边查找。若要找的值 大于 中间位置的数据则往右边查找。重复1和2若没有要找的值则返回false。
注二分查找的要求数据有序即已排好序。 时间复杂度最好情况 O(1)最坏情况 O(logn)平均情况 O(logn)
每次找中间位置每次查找范围减半查找次数最多logn因此总时间约 O(logn)。最好情况是第一个中间位置就是要找的值时间O(1)。
空间复杂度【迭代】O(1)【递归】 O(logn)
【迭代】只重复使用存储中间位置数据的空间不随数据量变动而变动因此空间使用是常量O(1)。【递归】需使用栈存储递归时的中间位置数据最多查找次数logn空间使用约 O(logn) 。 C代码实现
【迭代】
int search(int *array, int length, int data) // binary search
{// 起始索引结束索引中间位置索引int start 0, end length - 1;int midindex start ceil((end - start ) / 2);// 索引号越界退出循环while(midindex 0 midindex end){ // 找到匹配的值返回1trueif(array[midindex] data) return 1;// 找的值比中间值小往左边找结束索引为中间位置前一位if(array[midindex] data) end midindex - 1;// 找的值比中间值大往右边找开始索引为中间位置后一位else start midindex 1;// 循环找下一个中间位置midindex start ceil((end - start ) / 2);}// 没找到返回0falsereturn 0;
}
【递归】
int search2(int *array, int start, int end, int data) // binary search (recursion)
{// 获取中间位置索引int midindex start ceil((end - start ) / 2);// 索引号越界即没找到返回0falseif(midindex 0 || midindex end) return 0;// 找到值返回1trueif(array[midindex] data) return 1;// 要找的值 比中间值小往左边递归查找if(array[midindex] data) search2(array, 0, midindex - 1, data);// 要找的值 比中间值大往右边递归查找else search2(array, midindex 1, end, data);
} 完整代码binarysearch.c
#include stdio.h
#include math.hint search(int *, int, int); // binary search
int search2(int *, int, int, int); // binary search (recursion)
void traverse(int *, int); // show element one by one int main(void)
{int arr[] {1,2,3,5,6,8,9};int n sizeof(arr) / sizeof(int);traverse(arr, n); printf([no recursion] find 8 (1:true, 0:false): %d\n, search(arr, n, 8));printf([ recursion ] find 8 (1:true, 0:false): %d\n, search2(arr, 0, n, 8));printf([no recursion] find 4 (1:true, 0:false): %d\n, search(arr, n, 4));printf([ recursion ] find 4 (1:true, 0:false): %d\n, search2(arr, 0, n, 4));return 0;
}int search(int *array, int length, int data) // binary search
{int start 0, end length - 1;int midindex start ceil((end - start ) / 2);while(midindex 0 midindex end){if(array[midindex] data) return 1;if(array[midindex] data) end midindex - 1;else start midindex 1;midindex start ceil((end - start ) / 2);}return 0;
}int search2(int *array, int start, int end, int data) // binary search (recursion)
{int midindex start ceil((end - start ) / 2);if(midindex 0 || midindex end) return 0;if(array[midindex] data) return 1;if(array[midindex] data) search2(array, 0, midindex - 1, data);else search2(array, midindex 1, end, data);
}void traverse(int *array, int length) // show element one by one
{printf(elements(%d): , length);for(int k 0; k length; k){printf(%d , array[k]);}printf(\n);
} 编译链接 gcc -o binarysearch binarysearch.c 执行可执行文件 ./binarysearch
