首页 > 后端开发 > C++ > 正文

二分搜索(递归和迭代)在C程序中的实现

WBOY
发布: 2023-08-26 14:37:11
转载
932 人浏览过

二分搜索(递归和迭代)在C程序中的实现

二分搜索是一种用于在排序数组中查找元素(目标值)位置的搜索算法。在应用二分搜索之前,数组应该被排序。

二分搜索也被称为对数搜索、二分查找、半区间搜索。

工作原理

二分搜索算法通过将要搜索的元素与数组的中间元素进行比较,并根据此比较结果执行所需的过程。

情况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 <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
登录后复制

以上是二分搜索(递归和迭代)在C程序中的实现的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板