C中的二分搜索 |21xrx.com

C中的二分搜索

2021-07-07 07:09:04 深夜i -- --

C 中的二分搜索

C语言中的二分查找，在已排序的数组中查找元素。如果数组未排序，则必须使用排序技术（例如归并排序）对其进行排序。如果要搜索的元素存在于列表中，则我们打印其位置。该程序假定输入数字按升序排列。

C中的二分查找程序

#include <stdio.h>


int main()
{
  int c, first, last, middle, n, search, array[100];

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  printf("Enter value to find\n");
  scanf("%d", &search);

  first = 0;
  last = n - 1;
  middle = (first+last)/2;

  while (first <= last) {
    if (array[middle] < search)
      first = middle + 1;
    else if (array[middle] == search) {
      printf("%d found at location %d.\n", search, middle+1);
      break;
    }
    else
      last = middle - 1;

    middle = (first + last)/2;
  }
  if (first > last)
    printf("Not found! %d isn't present in the list.\n", search);

  return 0;
}

程序输出：

用于线性搜索的 C 程序

下载二进制搜索程序。

二分搜索比线性搜索快。它的时间复杂度为 O(log(n))，而线性搜索的时间复杂度为 O(n)。但是，列表应该按升序/降序排列，散列比二分搜索快，并且在恒定时间内执行搜索。

使用递归在 C 中进行二分搜索

#include <stdio.h>


int binarySearch(int [], int, int, int);

int main()
{
  int c, first, last, n, search, array[100], index;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  printf("Enter value to find\n");
  scanf("%d", &search);

  first = 0;
  last = n - 1;

  index = binarySearch(array, first, last, search);
 
  if (index == -1)
    printf("Not found! %d isn't present in the list.\n", search);
  else
    printf("%d is present at location %d.\n", search, index + 1);
 
  return 0;
}

int binarySearch(int a[], int s, int e, int f) {
  int m;
 
  if (s > e) // Not found
     return -1;

  m = (s + e)/2;

  if (a[m] == f)  // element found
    return m;
  else if (f > a[m])  
    return binarySearch(a, m+1, e, f);
  else
    return binarySearch(a, s, m-1, f);
}

我们将四个参数传递给 binarySearch 函数：数组它的第一个和最后一个索引，要搜索的元素。

如果需要，您还可以在数组的一部分中搜索元素。

上一篇: idea打包java可执行jar包

下一篇: C中的反向数组

评论区

()

相似文章