#arrays #sorting #search
#массивы #сортировка #Поиск
Вопрос:
Если у меня есть отсортированный (строго возрастающий) массив, где a[0] != 0, а a[0] <a[1], то не существует другого значения, которое могло бы равняться его значению, верно? Итак, кроме 0, a[i] != i ?
редактировать: неправильный оператор
Комментарии:
1. Повторения также не допускаются!
2. Нет, это неправда. Контрпример:
[1, 1.5, 2]3. Это было в пространстве N, о котором я говорил, следовало уточнить.
Ответ №1:
Если я вас правильно понял, у вас есть (по возрастанию) отсортированный массив только с целыми положительными числами, без дубликатов. Если a[0]> 0, то для всех i: a[i]>i . Это правда, доказательство индукции:
Инициализация:
для i= 0 это тривиально.
Шаг:
предположим, что условие выполняется для i (a[i]>i), докажите, что оно выполняется для i 1 (a[i 1]>i 1):
- a[i 1] > a[i]> i
- a[i 1] > a[i]> = i 1
- a[i 1] > i 1
qed.
Комментарии:
1. Отлично! Спасибо!