Почему не работает бинарный поиск?

Question

[Dmitriy]

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

int main() {
	int arr[7][7] = { {-5, -2, -1, 1, 6, 7, 8},
					{-91, 6, 6, 7, 7, 8, 9},
					{-10, -1, 6, 7, 8, 9, 10},
					{-1, -1, 7, 8, 8, 8, 9},
					{-10, -8, -5, -1, -1, 7, 8},
					{-3, -2, -1, -1, 6, 7, 8},
					{1, 4, 13, 22, 31, 40, 52},
					};

	for (int i = 0; i < 7; i++) {
		for (int j = 0; j < 7;j++) {
			printf("%d", arr[i][j]);
			printf(" ");
		}
		printf("\n");
	}
	int mid = 0;
	int left = 0;
	int right = 6;
	int k = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		
		if (arr[k][mid] > 5) {
			right = mid--;
		}
		else if (arr[k][mid] < 0) {
			left = mid++;
		}
		else {
			printf("Value is located at [%i]:[%i]!", k, mid);
			return 0;
		}
		k++;	
	}
	return 0;
}

Надо сделать поиск по матрице.
k - номер строки.
В чём проблема?
Ниже код на одномерный массив:

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


int main() {
	int arr2[7] = { -2, -1, 0, 1, 2, 3, 4 };
	printf("This is arr2!\n=============\n");
	for (int i = 0; i < 7; i++) {
		printf(" %i |", arr2[i]);	
	}
	printf("\n=============\n");

	int left = 0;
	int right = 6;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr2[mid] < 0) {
			left = mid + 1;
		}
		else if (arr2[mid] > 5) {
			right = mid - 1;
		}
		else {
			printf("Needed value is with index = %i!", mid);
			return 0;
		}
	}
	return 0;
}

Мне надо найти первый элемент из диапазона (0:5)
В данном примере, оно выводит индекс еденицы = 3.
Потому что середина начинается с этого индекса и это значение попадает в диапазон.
Как это исправить?
Если задавать какое-то конкретное число, то находит правильно!

Comments

[Владимир Олохтонов]

Проверьте сначала корректность реализации бинарного поиска на одной строке, а затем поместите его в цикл по строкам.

Сейчас у вас какая-то каша вместо программы.

[Dmitriy]

Владимир Олохтонов, обновил

Answer 1

[Владимир Олохтонов]

if (arr2[mid] < 0) {
      left = mid + 1;
    }
    else if (arr2[mid] > 5) {
      right = mid - 1;
    }
    else {

Вы сравниваете pivot с разными значениями. Какое число вы пытаетесь найти?

Comments

[Dmitriy]

{ -2, -1, -1, -1, 1, 2, 4 }
Вот массив, поиск должен найти самое левое число, которое лежит в диапазоне от 0 до 5

[Dmitriy]

Сейчас он находит элемента 2 с индексом 5, а должен 1 с индексом 4.
То есть он начинает с индекса 3, элемент пож этим индексом меньше 0, увеличивает левую границу, она будет 4, и дальше поиск производится с индекса 5 ( левая + правая ) / 2 = ( 4 + 6 ) /2, а должно получается чтоб 4 было

[Владимир Олохтонов]

Вообще говоря, бинарный поиск обычно применяется для поиска одного числа, а не целого диапазона.

Мне кажется проще всего будет просто поискать самое левое число ≥ 0.

Если оно окажется ≤ 5, то это и есть наш ответ, если же нет, то это означает, что ответа не существует, поскольку поиск вернул нам самое левое (то есть маленькое) число из соответствующих условию ≥ 0.

[Dmitriy]

Владимир Олохтонов, та я понимаю, но задача именно бинарным.
То есть если 1-ый ряд массива такой:
-5, -2, 1, 2, 2, 3, 3
Должно выводить 1 с индексом 2, а выводит 2 с индексом 3, так как 3 это середина

[Владимир Олохтонов]

Это и будет бинарный поиск, только реализованный более корректно.

Если вы упростите решаемую задачу, вам будет легче найти ошибку.

Распишу ещё раз чуть подробнее:
1) пишете левосторонний бинарный поиск по вот этой статье: https://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%...
2) ищете в массиве 0, получаете позицию в массиве, слева от которой все числа < 0, а справа все числа ≥ 0;
3) сравниваете число в найденной позиции с 5, если оно ≤ 5, то это ваш ответ, в противном случае числа из диапазона [0, 5] в массиве не существует;
4) прикручиваете сверху цикл по строкам матрицы.