X는 몇 자리입니까?

Question

[10424545616175901240]과 같은 배열이 주어지면 어떤 숫자 X가 그 사이에 있는지 어떻게 알 수 있습니까? 예를 들어, X = 59이면 대답은 [45,45,61,61]입니다.

선택 열거자를 위해 완벽하게 보이지만, 양쪽에있는 모든 요소를 ​​선택하는 방법을 알아낼 수 없습니다.

Answer 1

경계의 반복 된 값이 필요한 것 같습니다. 그렇습니까? 예를 들어 기능적 접근 방식이 있습니다. 그것은 O (n)입니다. 따라서 큰 입력 배열을 가지고 있다면 다른 사람들이 지적한 것처럼 O (log (n)) 이분법 알고리즘을 사용하는 것이 좋습니다 (참고 : 값은 xs.min과 xs.max 사이 여야 함).

xs = [10,42,45,45,61,61,75,90,1240] 
chk_pairs = xs.chunk { |x| x }.each_cons(2) 
boundaries = chk_pairs.detect { |_, (y, ys)| y > 59 }.flat_map { |x, xs| xs } 
#=> [45, 45, 61, 61] 

Answer 2

입력 배열이 항상 샘플로 정렬되어 있다고 가정하면 이진 검색을 사용하여 다음 더 높고 더 높은 (또는 같을 수도있는) 숫자를 찾을 수 있습니다. 특정 경우에, 당신은 분명히 그곳에서 왼쪽과 오른쪽을 보면서 처음에 발견 한 다음 하위/상위 숫자와 동일한 숫자를 찾습니다.