При выполении задачи всплывает ошибка. Задача по бинарному поиску внутри цикла - C (СИ)
Формулировка задачи:
#include <stdio.h>
int binsearch (int x, int v[], int n);
//Бинарный поиск
void main ()
{
int n = 20;
int a[n];
char i;
for (i = 0; i <n; i++)
a[i] = i*5;
printf ("%d\n",binsearch(30,a,n));
return;
}
int binsearch (int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while ((low <= high) && (x!=v[mid]))
{
mid = (low + high)/2;
if (x < v[mid])
high = mid - 1;
else
low = mid + 1;
}
printf("%d\n",mid);
if (x==v[mid]) return mid;
return -1;
}Решение задачи: «При выполении задачи всплывает ошибка. Задача по бинарному поиску внутри цикла»
textual
Листинг программы
int binsearch (int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
mid = 0;
while ((low <= high) && (x!=v[mid]))
{
mid = (low + high)/2;
if (x < v[mid])
high = mid - 1;
else
low = mid + 1;
}
printf("%d\n",mid);
if (x==v[mid]) return mid;
return -1;
}
Объяснение кода листинга программы
- В функции
binsearchопределяются следующие переменные:x- значение, которое нужно найти в массивеv.v[]- массив, в котором нужно найти значениеx.n- размер массиваv[].
- Затем определяются следующие переменные:
low- инициализируется значением 0, это индекс левой границы диапазона поиска в массивеv[].high- инициализируется значениемn - 1, это индекс правой границы диапазона поиска в массивеv[].mid- инициализируется значением 0, это первый средний индекс в диапазоне поиска.
- Затем выполняется цикл
while, который будет выполняться до тех пор, покаlowне станет большеhighилиxне будет равноv[mid]. - Внутри цикла
midобновляется на(low + high)/2, это новый средний индекс. - Затем выполняется проверка
if (x < v[mid]), если она истинна, то значениеhighобновляется наmid - 1, тем самым смещая правую границу диапазона поиска влево. - Если проверка
if (x < v[mid])ложна, то значениеlowобновляется наmid + 1, тем самым смещая левую границу диапазона поиска вправо. - После выхода из цикла
whileвыполняется операцияprintf(%d\n,mid);, которая выводит индекс среднего элемента, где был найден элементx. - Затем выполняется проверка
if (x==v[mid]), если она истинна, то возвращается значениеmid. - Если проверка
if (x==v[mid])ложна, то возвращается значение-1, что означает, что элементxне найден в массивеv[].