binary search:ソート配列から特定の数のカウントを求める

問題の定義
N個の要素を含む数列を昇順に並べます.このとき、この数列にxが現れる回数を計算してください.
例えば、数列{1、1、2、2、2、3}がある場合、x=2は、現在の数列に2の値を持つ要素が4つあるため、4を出力する.
しかし,アルゴリズムを時間複雑度O(logn)として設計しなかった場合,この問題はタイムアウトと判定される.
入力条件

の第1行において、Nおよびxは整数で区切られて入力される.(1 <= N <= 1,000,000)

行目に入力されたN個の要素は、整数でスペースで区切られています.

しゅつりょくじょうけん
出力値xの数列要素の個数.要素値がxでない場合は、-1が出力されます.
I/O例

# 입력
7 2
1 1 2 2 2 2 3
# 출력
4

私が作ったコード

from bisect import bisect_left, bisect_right

n, x = map(int, input().split(" "))
lst = list(map(int, input().split(" ")))
lst = [1,1,2,2,2,2,3]
lst.sort(reverse=False)
x = 2
result = bisect_right(lst, x) - bisect_left(lst, x)

if result == 0:
    print(-1)
else:
    print(result)

正しいコード

from bisect import bisect_left, bisect_right

def count_by_range(arr, left_value, right_value) :
  right_index = bisect_right(arr, right_value)
  left_index = bisect_left(arr, left_value)
  return right_index - left_index

n, x = map(int, input().split())
arr = list(map(int, input().split()))

result = count_by_range(arr, x, x)

if result != 0 :
  print(result)
else :
  print(-1)

考察する

の正解コードと同じようによく書かれています.

Pythonでこのように役に立つ関数をよく覚えておきましょう.