Упражнения C: бинарный поиск

Алгоритм поиска и сортировки при программировании на C: упражнение 1 с решением

Напишите программу на C для бинарного поиска.
Примечание. Бинарный поиск. В компьютерных науках алгоритм бинарного поиска или поиска с полуинтервалом находит позицию целевого значения в отсортированном массиве. Алгоритм двоичного поиска может быть классифицирован как алгоритм поиска типа «разделяй и властвуй» и выполняется в логарифмическом времени.
Учитывая отсортированный массив arra [] из n элементов, напишите функцию для поиска заданного элемента x в arra [].

Наглядная презентация - Алгоритм двоичного поиска:

Пример решения:

Код C:

#include<stdio.h>
  void main()
  {
  int  arra[100],i,n,x,f,l,m,flag=0;
  printf("Input no. of elements in  an array\n");
  scanf("%d",&n);
  printf("Input  %d value in ascending order\n",n);
  for(i=0;i<n;i++)
  scanf("%d",&arra[i]);
  printf("Input  the value to be search : ");
  scanf("%d",&x);
  /* Binary Search  logic */
  f=0;l=n-1;
  while(f<=l)
  {
  m=(f+l)/2;
  if(x==arra[m])
  {
  flag=1;
  break;
  }
  else  if(x<arra[m])
  l=m-1;
  else
  f=m+1;
  }
  if(flag==0)
  printf("%d  value not found\n",x);
  else
  printf("%d value  found at %d position\n",x,m);
  }

Пример вывода:

 Вход № элементов в массиве                                                                            
3                                                                                                             
Введите значение 3 в порядке возрастания                                                                             
15                                                                                                            
18                                                                                                            
20                                                                                                            
Введите значение для поиска: 15                                                                            
15 значение найдено в 0 позиции

Блок - схема:

Редактор кода программирования C:

Улучшите этот пример решения и опубликуйте свой код через Disqus.

Предыдущий: C Алгоритм поиска и сортировки
Далее: Напишите программу на C для сортировки списка элементов с использованием алгоритма сортировки выбора.