C程序中的二进制搜索（递归和迭代）
二进制搜索是一种搜索算法，用于查找排序数组中元素（目标值）的位置。在应用二进制搜索之前，应先对数组进行排序。
这些名称也称为二进制搜索，对数搜索，二进制印章，半间隔搜索。
加工
二进制搜索算法通过比较要由数组中间元素搜索的元素来工作，并基于此比较遵循所需的过程。
情况1-元素=中间，找到的元素返回索引。
情况2-元素>中间，在子数组中搜索从中间+1索引到n的元素。
情况3-元素<中间，在子数组中搜索从0索引到中间-1的元素。
算法
参数inital_value，end_value
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 <stdio.h>
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 <stdio.h>
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