二分探索(ギザギザの場合)について
概要
- 単純増加やきれいに別れているわけではないarrayにおいて、その境界を求めようとすると、3つ以上の条件が必要になる
- 2分探索の特殊系であるが、3分探索とは言わないらしい
具体例
- 数列がある時、単調増加が一箇所破綻している箇所を見つける
def bisect(ng, ok, lst):
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if lst[ng] < lst[mid] > lst[ok]:
ng = mid
elif lst[ng] > lst[mid] < lst[ok]:
ok = mid
elif lst[ng] < lst[mid] < lst[ok]:
ok = ng
else:
pass
return ok
def solve(lst):
if len(lst) == 2:
return min(lst)
ng = 0
ok = len(lst)-1
idx = bisect(ng, ok, lst)
return lst[idx]
assert solve([4,5,6,7,0,1,2]) == 0
assert solve([3,4,5,1,2]) == 1
assert solve([11,13,15,17]) == 11
具体例
- 数列が増加と減少を繰り返す時、どこかのピークを見つける
def bisect(ng, ok, lst):
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if lst[mid] < lst[mid+1]:
ng += 1
else:
ok = mid
return ng if lst[ng] >= lst[ok] else ok
def solve(lst):
ng = 0
ok = len(lst)-1
idx = bisect(ng, ok, lst)
print(idx)
return idx
assert solve([1,2,3,1]) == 2
assert solve([1,2,1,3,5,6,4]) == 5