두 위치의 차이
배열이 2, 4, 4, 7, 9일 때 값이 4 이상 7 이하인 항목은 세 개다. 처음으로 4 이상이 되는 위치는 0부터 세면 1이고 처음으로 7보다 커지는 위치는 4다. 두 위치의 차이 4에서 1을 뺀 값이 개수가 된다. 항목을 하나씩 읽는 대신 원하는 구간을 감싸는 위치를 찾는 방법이다.
끝값의 포함 여부
하한 L과 상한 R을 모두 포함하면 처음으로 L 이상인 위치와 처음으로 R보다 큰 위치를 사용한다. 상한을 제외하는 구간이라면 끝 위치는 처음으로 R 이상인 곳이다. 문서에서 구간을 닫힌 구간인지 반열린 구간인지 명시하지 않으면 같은 입력으로 다른 답을 만들 수 있다.
중복과 빈 결과
동일한 값이 여러 번 있으면 어떤 한 항목을 찾는 검색만으로 개수를 알 수 없다. 중복 묶음의 양쪽 경계를 찾아야 한다. 해당 값이 전혀 없으면 두 경계가 같아져 개수가 0이 된다. 모든 값보다 작은 구간이나 큰 구간도 위치가 배열 양 끝으로 수렴하도록 처리하면 별도의 임의 보정이 줄어든다.
정렬 전제와 변경 비용
배열이 검색에 사용하는 키 순서로 정렬되어 있어야 한다. 다른 기준으로 정렬된 결과에 같은 경계 검색을 적용할 수는 없다. 검색 두 번은 일반적으로 O(log N)이지만 정렬을 처음 만드는 비용이나 배열 중간에 항목을 삽입하는 비용은 별개다. 변경이 잦다면 조회 횟수와 갱신 비용을 함께 비교한다.
잘못된 구간의 처리
L이 R보다 큰 입력에서는 빈 구간을 반환하거나 오류로 처리하는 규칙을 정한다. 경계 위치를 무조건 빼기만 하면 음수가 나올 수 있다. 또한 비교 중 데이터가 바뀌면 처음 경계를 찾았을 때와 두 번째 경계를 찾았을 때의 배열이 달라질 수 있으므로 일관된 입력을 기준으로 계산해야 한다.
관련 문서
이진 탐색의 경계 조건 / 이진 탐색 / 배열