二分搜索是一种用于在排序数组中查找元素（目标值）位置的搜索算法。在应用二分搜索之前，数组应该被排序。
二分搜索也被称为对数搜索、二分查找、半区间搜索。
工作原理
二分搜索算法通过将要搜索的元素与数组的中间元素进行比较，并根据此比较结果执行所需的过程。
情况1 – 元素 = 中间值，找到元素并返回索引。
情况2 – 元素 > 中间值，在从中间+1索引到n的子数组中搜索元素。
情况3 – 元素
算法
参数初始值，结束值
Step 1 : Find the middle element of array. using ,middle = initial_value + end_value / 2 ;Step 2 : If middle = element, return ‘element found’ and index.Step 3 : if middle > element, call the function with end_value = middle - 1 .Step 4 : if middle < element, call the function with start_value = middle + 1 .Step 5 : exit.
二分搜索算法的实现函数使用了反复调用函数。这个调用可以有两种类型：
迭代调用是多次循环同一段代码。
递归调用是反复调用同一个函数。
使用迭代调用实现二分搜索的程序
示例
演示
#include int iterativeBinarySearch(int array[], int start_index, int end_index, int element){ while (start_index <= end_index){ int middle = start_index + (end_index- start_index )/2; if (array[middle] == element) return middle; if (array[middle] < element) start_index = middle + 1; else end_index = middle - 1; } return -1;}int main(void){ int array[] = {1, 4, 7, 9, 16, 56, 70}; int n = 7; int element = 16; int found_index = iterativeBinarySearch(array, 0, n-1, element); if(found_index == -1 ) { printf("Element not found in the array "); } else { printf("Element found at index : %d",found_index); } return 0;}
输出
Element found at index : 4
使用递归调用实现二分查找的程序
示例
在线演示
#include int recursiveBinarySearch(int array[], int start_index, int end_index, int element){ if (end_index >= start_index){ int middle = start_index + (end_index - start_index )/2; if (array[middle] == element) return middle; if (array[middle] > element) return recursiveBinarySearch(array, start_index, middle-1, element); return recursiveBinarySearch(array, middle+1, end_index, element); } return -1;}int main(void){ int array[] = {1, 4, 7, 9, 16, 56, 70}; int n = 7; int element = 9; int found_index = recursiveBinarySearch(array, 0, n-1, element); if(found_index == -1 ) { printf("Element not found in the array "); } else { printf("Element found at index : %d",found_index); } return 0;}
输出
Element found at index : 3
以上就是二分搜索（递归和迭代）在C程序中的实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1443443.html
微信扫一扫 
支付宝扫一扫 
