Дать массив целых чисел был отсортирован (неубывающий порядок), нам нужно найти индекс минимального номера, который больше заданного ключа, я написал две функции, они идентичны, за исключением возвратных линий.Найдите индекс минимального числа, который больше заданного ключа сортированного массива, выполняют ли эти две функции одинаковый результат?
ло и привет указать индекс низких и высоких один, включая
int minimum_index_greater(int *a, int lo, int hi, int key) {
int left = lo - 1;
int right = hi + 1;
while (left + 1 < right) {
int mid = (left + right)/2;
if (a[mid] > key) right = mid;
else left = mid;
}
return right; -------> function 1
return left + 1; -------> function 2
}
Первый вопрос любой из них правильно (возвращает правильное значение)?
Второй вопрос: I Предположим, что в этой ситуации две функции одинаковы, они возвращают одинаковое значение в каждом случае. И я в этом уверен. Я прав или нет? пожалуйста, объясни.
P/S: Когда я решаю проблему на Sphere Online Judge. Мне нужно найти это значение и решить проблему, использовать функцию 1, я получил 97,72/100 баллов (что я понятия не имею, почему это не 100), используйте функцию 2, я получил только 94.44. Так что я думаю, проблема здесь
Что означают 'lo' и' hi'? Я предполагаю, что указать диапазон индексов для поиска, но является ли 'hi' эксклюзивным или включенным? –
Прошу прощения, lo и hi являются низкими и высокими, чтобы указать диапазон индексов, и они все включено. – dandoh
теоретически возвращенные два значения будут одинаковыми. Однако мне кажется, что вы получили начальное значение для левого и правого неправильного. Вы уверены, что вам нужно использовать 'lo - 1' и' hi + 1' вместо 'lo + 1' и' hi - 1'. Обычно я реализую двоичный код аналогично, и в моей реализации левый конец является включительным, а правый - исключительным. Это означало бы, что вам нужно использовать 'lo' и' hi + 1' (если оба конца изначально включены). –