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)

Recommended Posts

Algorithm in Python (binary search)
Binary search in Python
Binary search in Python (binary search)
Algorithm in Python (ABC 146 C Binary Search
Binary search in Python / C ++
Algorithm in Python (breadth-first search, bfs)
Algorithm in Python (depth-first search, dfs)
Algorithm learned with Python 10th: Binary search
Genetic algorithm in python
Binary search (python2.7) memo
[Python] Binary search ABC155D
Algorithm in Python (Bellman-Ford)
Linear search in Python
Binary search with python
Binary search with Python3
Algorithm in Python (Dijkstra's algorithm)
Algorithm in Python (primality test)
Search for strings in Python
Search algorithm using word2vec [python]
Reproduce Euclidean algorithm in Python
Implement Dijkstra's Algorithm in python
Python algorithm
Sorting algorithm and implementation in Python
Save the binary file in Python
Write A * (A-star) algorithm in Python
Develop an investment algorithm in Python 2
Create a binary file in Python
Write a depth-first search in Python
[C language algorithm] Binary search tree
Implementing a simple algorithm in Python 2
Algorithm (segment tree) in Python (practice)
Run a simple algorithm in Python
Depth-first search using stack in Python
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
Algorithm learned with Python 9th: Linear search
Meta-analysis in Python
Python memorandum (algorithm)
Unittest in python
Ant book in python: Sec.2-5 Dijkstra's algorithm
Try working with binary data in Python
Search and play YouTube videos in Python
Epoch in Python
Discord in Python
Search the maze with the python A * algorithm
Sudoku in Python
DCI in Python
visualize binary search
quicksort in python
nCr in python
N-Gram in Python
String search algorithm
Programming in python
Plink in Python
Constant in python
ABC146C (binary search)
Write a simple greedy algorithm in Python
Lifegame in Python.