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

Question

[cicatrix]

Есть предварительно отсортированный массив A из N целочисленных значений.
Требуется определить является ли он непрерывным, т.е. A[n+1] = A[n]+1 и разбить этот массив на подмассивы, где бы это условие соблюдалось.

Пока ничего в голову, кроме тупого перебора на проверку условия A[n+1] = A[n]+1 не пришло, хотел спросить, есть ли более быстрые способы?

Comments

[Lander]

Более быстрый способ - это использование функции explode_array_by_gap()?

[Сергей Герасимов]

Думаю что тут могут помощь функции array_unique и array_diff, но насколько это менее затратно, чем ваш вариант...

[Lander]

Сергей Герасимов, Так про php речь то вроде и не шла...

[Сергей Герасимов]

Lander, чтож =)

[Максим Тимофеев]

кроме тупого перебора

а что в переборе тупого?
На самом деле Вы говорите "мне надо сложить 2 и 3, но не использовать же плюс для этого". Как по мне - перебор очевидное и правильное решение.

Answer 1

[#]

шаг значения фиксированный?
это "1" ?

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

A[n]

как исходного массива, так и фрагмента. по отклонению можно делать вывод о наличии пропуска (или нескольких)

надо помнить, что двиочная выборка будет эффективна в плане определения непрерывных фрагментов, для уточнения разрывов, может потребоваться эвристическая модификация алгоритма

ps SharuPoNemnogu точно!.. в общем случае, все рассуждения об арифметической прогрессии и двоичном поиске, верны для любого шага прогрессии (не только 1)

Answer 2

[SharuPoNemnogu]

это арифметическая прогрессия. Сумму элементов массива сравниваем с суммой прогрессии, если не равны запускаем двоичный поиск как написал mindtester , внутри можно так же чекать суммы