21xrx.com
2024-03-29 09:43:15 Friday
登录
文章检索 我的文章 写文章
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 函数:数组它的第一个和最后一个索引,要搜索的元素。

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

  
  
下一篇: C中的反向数组

评论区

{{item['qq_nickname']}}
()
回复
回复