Algorithm in Python (binary search)

Introduction

I was free due to the influence of the coronavirus ... (Omitted below) Since the previous Seg tree was heavy, this time I will summarize the binary search that can be implemented relatively easily.

Way of thinking

If some boundary meets and does not meet, you can search for that boundary with ** O (logN) **. For example, suppose you are given the following list, with ** x ** for those that do not meet the conditions and ** o ** for those that meet. 　　　　　　　　　　　xxxxxxoooooo

Considering 0-index, binary search is effective when you want to find the 5th or 6th (either left or right of the boundary). Assign the left side of the search range to the variable ** left ** and the right side to the variable ** right **. Add these and divide by 2 (truncated) as ** mid **, and determine whether the element with index ** mid ** satisfies the condition. If so, there is no boundary to the right of it, so update the value of ** right ** to ** mid ** and truncate the right side. On the contrary, if it is not satisfied, there is no boundary to the left of it, so update the value of ** left ** to ** mid **. In this way, the section is narrowed by half each time, and finally the search ends when ** right ** and ** left ** are next to each other. At this time, ** right ** always has the index of the element that satisfies the condition, and ** left ** has the index of the element that does not satisfy, so in the above example, ** left ** is 5, ** right ** has a value of 6.

Example 1

In ** [2, 5, 7, 9, 10, 18, 29] **, consider the smallest index that is 9 or more. If the condition is 9 or more, it will be ** xxxoooo ** whether it is satisfied or not, so the final answer is the value of ** right **.

code

a = [2, 5, 7, 9, 10, 18, 29]

left = 0
right = len(a) - 1

while right - left > 1:
    mid = (right + left) // 2
    if a[mid] >= 9:
        right = mid
    else:
        left = mid

print(right) # 3

Example 2

Since it is a big deal, solve ** Buy an integer ** of ABC146-C from the past questions of atcoder. Again, there is a boundary that you can buy the left side and not the right side of the candidates 1 to 10 ^ 9, so you can do a binary search. This time we will search for integers directly instead of indexes. (If you make a list, it's TLE) As a caveat, if you can't buy one and if you can buy all, there is no boundary, so it seems better to separate the cases.

code

import sys

a, b, x = [int(x) for x in input().split()]

left = 1
right = 10**9

if a*right + b*len(str(right)) <= x:
    print(right)
    sys.exit()

if a*left + b*len(str(left)) > x:
    print(0)
    sys.exit()

while right - left > 1:
    mid = (right + left) // 2
    if a*mid + b*len(str(mid)) <= x:
        left = mid
    else:
        right = mid

print(left)

Standard library bisect

It can be used for binary search to determine whether it is included in the list and for finding the index containing the element you want to insert. You can make this yourself because there is self-made in the past, but it is normal to use the standard library ** bisect **. think. (I think it is necessary to practice how to use it)