二分查找算法是一种基于比较和分割机制的算法。二分搜索算法也称为半间隔搜索、对数搜索或二分查找。二分查找算法,在已排序数组中查找目标值的位置。它将目标值与数组的中间元素进行比较。如果该元素等于目标元素,则算法返回找到的元素的索引。如果它们不相等,则搜索算法使用该数组的一半部分,根据值的比较,算法使用前半部分(当值小于中间时)和后半部分(当值小于中间时)当该值大于中间值时)。对下一个数组的一半执行相同的操作。
Input: A[] = {0,2,6,11,12,18,34,45,55,99} n=55 Output: 55 at Index = 8
对于我们的数组 -
我们将比较 55 和数组的中间元素 18,它小于 55所以我们将使用数组的后半部分,即数组 {24, 45, 55, 99},中间也是 55。用它检查搜索元素的值。并且匹配到的值,那么我们将返回该值的索引为8。
如果搜索元素小于中间,那么我们将使用前半部分并继续直到元素在数组的中间找到。
为了实现二分查找,我们可以用两种方式编写代码。这两种方式仅与我们调用检查二分搜索元素的函数的方式不同。它们是:
使用迭代 - 这意味着在函数内使用循环来检查中间元素的相等性。
使用 在此方法中,函数使用一组不同的值一次又一次地调用自身。
#include<stdio.h> int 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 </p><p>",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
#include<stdio.h> int 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 </p><p>",n,RecursiveBsearch(A,0,9,n)); return 0; }
55 is found at Index 8
以上是二分查找的C程序(递归和迭代)的详细内容。更多信息请关注PHP中文网其他相关文章!