Откуда появляется ошибка?

Question

[Pinkman]

Всем привет! Я писал простенький алгоритм из книжки на си.
Алгоритм бинарного поиска.
Но когда решил проверить его работоспособность, встретил странную ошибку. При значении длинны массива больше 10 000(ну и элементы там получается тоже от 1 до 10 000), то когда я выхожу за рамки этих значений.(т.е. ищу в массиве число 10001 или -1), то начинает выдавать ошибку: segmentation fault (core dumped). Но при значении(и длинны массива и его содержимом) до 10 000, а т.е. 1000 или 100, всё работает как надо, и если искомое число не находится, то возвращается 0.
Нашёл ещё ошибку. Если length = 2147483647, то программа вообще отказывается работать.

#include <stdio.h>
#include <stdlib.h>

const unsigned int length = 10000; 

int		binary_search(int *arr, int item)
{
	unsigned int low;
	unsigned int high;
	unsigned int mid;
	int			 guess;

	low = 0;
	high = length - 1;
	while (low <= high)
	{
		mid = high + low;
		guess = arr[mid];
		if (guess > item)
			high = mid - 1;
		else if (guess < item)
			low = mid - 1;
		if (guess == item)
			return (arr[mid]);
	}
	return (0);
}

int		main(int argc, char **argv)
{
	int arr[length];
	unsigned int count;

	count = 0;
	while (count < length)
	{
		arr[count] = count + 1;
		count++;
	}
	printf("%i", binary_search(arr, atoi(argv[1])));
	return (0);
}

Answer 1

[jcmvbkbc]

mid = high + low;
guess = arr[mid];

Первая очевидная ошибка здесь: сумму надо бы разделить пополам.

else if (guess < item)
  low = mid - 1;

Вторая очевидная ошибка здесь: mid может быть равен 0, а значит low может вылезти за пределы массива снизу.

С условием выхода из цикла поиска при отсутствии искомого значения в массиве тоже не всё ОК.

int arr[length];
Если length = 2147483647, то программа вообще отказывается работать.

Ты пытаешься разместить массив размером 8ГБ на стеке. Как видишь, это не очень хорошая идея.

Comments

[Pinkman]

Да не сам алгоритм интересует. А про память , только сейчас решил подумать на счёт этого, в голову даже как то не приходило...спасибо за ответ!

Answer 2

[User700]

int arr[length];

int		main(int argc, char **argv)
{
    ...
}

Объявите массив как глобальную переменную чтобы эта память была не на стеке. Или используйте malloc (+ free) для динамического выделения её в куче.