二分查找算法是一种基于比较和分割机制的算法。二分搜索算法也称为半间隔搜索、对数搜索或二分查找。二分查找算法，在已排序数组中查找目标值的位置。它将目标值与数组的中间元素进行比较。如果该元素等于目标元素，则算法返回找到的元素的索引。如果它们不相等，则搜索算法使用该数组的一半部分，根据值的比较，算法使用前半部分（当值小于中间时）和后半部分（当值小于中间时）当该值大于中间值时）。对下一个数组的一半执行相同的操作。
Input:A[] = {0,2,6,11,12,18,34,45,55,99}n=55Output:55 at Index = 8
解释
对于我们的数组 –
我们将比较 55 和数组的中间元素 18，它小于 55所以我们将使用数组的后半部分，即数组 {24, 45, 55, 99}，中间也是 55。用它检查搜索元素的值。并且匹配到的值，那么我们将返回该值的索引为8。
如果搜索元素小于中间，那么我们将使用前半部分并继续直到元素在数组的中间找到。
为了实现二分查找，我们可以用两种方式编写代码。这两种方式仅与我们调用检查二分搜索元素的函数的方式不同。它们是：
使用迭代 – 这意味着在函数内使用循环来检查中间元素的相等性。
使用 在此方法中，函数使用一组不同的值一次又一次地调用自身。
示例
#includeint iterativeBsearch(int A[], int size, int element);int main() { int A[] = {0,12,6,12,12,18,34,45,55,99}; int n=55; printf("%d is found at Index %d ",n,iterativeBsearch(A,10,n)); return 0;}int iterativeBsearch(int A[], int size, int element) { int start = 0; int end = size-1; while(start<=end) { int mid = (start+end)/2; if( A[mid] == element) { return mid; } else if( element < A[mid] ) { end = mid-1; } else { start = mid+1; } } return -1;}
输出
55 is found at Index 8
示例
#includeint RecursiveBsearch(int A[], int start, int end, int element) { if(start>end) return -1; int mid = (start+end)/2; if( A[mid] == element ) return mid; else if( element < A[mid] ) RecursiveBsearch(A, start, mid-1, element); else RecursiveBsearch(A, mid+1, end, element);}int main() { int A[] = {0,2,6,11,12,18,34,45,55,99}; int n=55; printf("%d is found at Index %d ",n,RecursiveBsearch(A,0,9,n)); return 0;}
输出
55 is found at Index 8
以上就是二分查找的C程序（递归和迭代）的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444547.html
微信扫一扫 
支付宝扫一扫 
