Как сделать бинарный поиск на си?

Question

[Егор]

Получается бесконечный цикл, что делать? И как узнать найдено ли число?

#include <stdio.h>
#define SIZE 10

int main (void){
  int array_1[SIZE], count_1, count_2, reserve, search, left, right, mid;
 
  for (count_1 = 0; count_1 < SIZE; count_1++){
    printf ("Enter array (%d): \t", SIZE - count_1);
    scanf ("%d", &array_1[count_1]);
  }  
  
  printf ("%s%10s \n", "Element", "Value");

  for (count_1 = 0; count_1 < SIZE; count_1++){
    printf ("%7d%10d \n", count_1, array_1[count_1]);
  }

  for (count_1 = 0; count_1 < SIZE - 1; count_1++){
    for (count_2 = 0; count_2 < SIZE - count_1 - 1; count_2++){
      if (array_1[count_2] > array_1[count_2 + 1]){
        reserve = array_1[count_2];
        array_1[count_2] = array_1[count_2 + 1];
        array_1[count_2 + 1] = reserve;
      }
    }
  }  

  printf ("%s%10s \n", "Element", "Value");
  
  for (count_1 = 0; count_1 < SIZE; count_1++){
    printf ("%7d%10d \n", count_1, array_1[count_1]);
  }

  printf ("Enter value: \t");
  scanf ("%d", &search);

  left = array_1[0];
  right = array_1[SIZE - 1];
  mid = (left + right) / 2;

  while (left <= right){
    if (search < array_1[mid]){
      left = mid - 1; 
    } else{
      right = mid + 1;  
    }
  }

  return 0;
}

Answer 1

[Rsa97]

Вполне логично, что цикл бесконечен.
Во-первых, изначально left и right почему-то задаются не индексами, а значениями из массива. Во-вторых mid должен рассчитываться на каждом шаге цикла. В третьих, отсутствует проверка на нахождение нужного значения. В четвёртых неправильно сдвигаются границы left и right внутри цикла.
Используйте отладчик и выполните участок программы пошагово с контролем всех переменных, а ещё лучше выполните его в уме, записывая результат каждого шага на бумаге.

Answer 2

[Егор]

Не знаю на сколько это правильно, но работает =) Спасибо.

#include <stdio.h>
#define SIZE 10

int main (void) {
  int arrayOne [SIZE], countOne, countTwo, reserve, search, left, right, mid;
  
  for (countOne = 0; countOne < SIZE; countOne++) {
    printf ("Enter array (%d): \t", SIZE - countOne);
    scanf ("%d", &arrayOne [countOne]);
  }

  printf ("%s%10s \n", "Element", "Value");

  for (countOne = 0; countOne < SIZE - 1; countOne++) {
    for (countTwo = 0; countTwo < SIZE - countOne - 1; countTwo++) {
      if (arrayOne [countTwo] > arrayOne [countTwo + 1]) {
        reserve = arrayOne [countTwo];
        arrayOne [countTwo] = arrayOne [countTwo + 1];
        arrayOne [countTwo + 1] = reserve;
      } 
    }
  }

  for (countOne = 0; countOne < SIZE; countOne++) {
    printf ("%7d%10d \n", countOne, arrayOne [countOne]);
  }

  printf ("Enter value: \t");
  scanf ("%d", &search);

  left = 0;
  right = SIZE - 1;

  while (left < right) {
    mid = (left + right) / 2;
    if (search <= arrayOne [mid]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  if (search == arrayOne [right]) {
    printf ("Ok! \n");
  } else {
    printf ("No! \n");
  }

  return 0;
}

Answer 3

[abcd0x00]

Как сделать бинарный поиск на си?

Он уже сделан - функция bsearch().