Confirmation of basic matters of competition professional ~ Binary search ~

It's easy to forget how to use the binary search function in competitive programming, so I'll keep it as a memorandum. Also, please note that this article does not cover what a binary search looks like. In addition, please note that this article is intended to confirm ** basic usage **.

Binary search in Python (bisect module)

In Python, the bisect module handles functions related to binary search. This module supports working with the ** (ascending) sorted list ** in order.

In competitive programming, the following two functions are mainly used. In the following, the element to be examined is x, the ** (ascending) sorted list ** to be examined is a, the first argument is a, and the second argument is x. In the 3rd and 4th arguments, you can specify the range to be examined in a, but it is not dealt with here. See bisect module.

①bisect_left Returns the index of the insertion point to a on the far left of x (in order). $ \ leftrightarrow Returns the index of the smallest element above $ x. $ \ leftrightarrow $ The element to the left is the largest (index) element smaller than x.

②bisect_right Returns the index of the insertion point to a on the far right of x (in order). $ \ leftrightarrow Returns the index of the smallest element that is larger than $ x. $ \ leftrightarrow $ The element to the left is the largest (index) element below x.

Binary search in C ++ (lower_bound and upper_bound ))

In C ++, the algorithm library handles functions related to binary search. This library works with any data structure ** if you have an iterator that meets the requirements of the algorithm **.

In competitive programming, the following two functions are mainly used. Also, as before, let x be the element you want to check, and let a be the ** (ascending) sorted array ** to check. At this time, specify the range to be examined with the first argument as a.begin () and the second argument as a.end (), and specify the element x to be examined in the third argument.

①lower_bound Synonymous with Python's leap year_left, but returns the smallest element ** iterator ** with x or greater elements. Also, if you want to get the smallest ** index **, you can get it with (return value) -a.begin ().

②upper_bound Synonymous with Python's leap year, but returns the ** iterator ** of elements larger than x and the smallest. Also, if you want to get the smallest ** index **, you can get it with (return value) -a.begin ().

bonus

✳︎ It needs to be an ascending sorted list, but you can sort it even if it is not in ascending order by overloading the operator. ✳︎ If you want to know more about lower_bound and upper_bound in C ++, please refer to this article. ✳︎ If you have any other important things, please let us know in the comments!