めぐる式二分探索について
解決したいこと
Python初学者です。paizaラーニングで、二分探索について学んでいます。めぐる式という方法を発見し、実践してみているのですが、タイムオーバーになってしまいます。
参考にしたサイト:
めぐる式二分探索
https://twitter.com/meguru_comp/status/697008509376835584
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
https://qiita.com/drken/items/97e37dd6143e33a64c8c
発生している問題・エラー
https://paiza.jp/works/mondai/binary_search/binary_search__basic_boss
paizaレベルアップ問題集 二分探索メニュー「ある範囲に含まれている整数の個数」の問題がタイムオーバーになってしまいます。
n=1000のときは通りますが、n=5000になると通らなくなります。
lower_boundとupper_boundを個別に動かしたときは、問題なく動作しました。
めぐる式に沿った方法で、どこでエラーが発生（もしくはループ）が教えていただけますと幸いです！
n=int(input())
a=list(map(int,input().split()))
srt_a=sorted(a)
q=int(input())
def lower_solve(mid,x):
if(srt_a[mid]>=x):
return True
else:
return False
def upper_solve(mid, x):
if(srt_a[mid] > x):
return True
else:
return False
def lower_bound(ng,ok,i): #lower_bound
while(abs(ok-ng)>1):
mid=ok+ng//2
if(lower_solve(mid,i)):
ok=mid
else:
ng=mid
return ok
def upper_bound(ng, ok, i): #upper_bound
while(abs(ok-ng) > 1):
mid = ok+ng//2
if(upper_solve(mid, i)):
ok = mid
else:
ng = mid
return ok
for i in range(q):
l,r=map(int,input().split())
print(upper_bound(-1, n, r)-lower_bound(-1, n, l))
#lower_bound <= xx < upper_boundより、upper_bound-lower_boundで間の個数を数える
0
