Write a binary search in Python

TL;DR

――It's a basic point, but in order to keep it in mind, I will write the code for binary search and summarize the explanation in Python. ――I will write the code myself for studying (without using the standard module for binary search). ――Since I was originally a graduate of a school in the design field, please forgive me for any knowledgeable points in the computer science field.

What to use

What is binary search?

Binary search is one of the algorithms for searching values for a sorted array. Also known as a binary search.

The condition is that the array to be searched is sorted, but it has the property that the search is less likely to slow down even if the target list becomes larger than a normal search.

The method is to first get the value in the center of the list and then compare whether the value in the center is larger or smaller than the value you are searching for.

If the value to be searched is smaller than the center value of the array, this time, the range of the array is narrowed down from the left edge to the range before the center value.

On the other hand, if the value to be searched is larger than the center value, the range of the array is narrowed down from the value one right of the center value to the right end of the array.

After that, the center value is taken in the range of the narrowed array, and it is judged again whether the value to be searched is larger or smaller than the center value, and the array is narrowed down.

If the value to be searched matches the value in the center of the array, it means that the value to be searched has been found, and the search ends there.

Consider the case where you search for the value of 2 in the sorted list[1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8].

First, get the value in the center of the list. The first median value is 4. The value 2 to be searched is smaller than the median value 4, so narrow the list to the left of the 4 part and get the value[1, 1, 2, 3, 3]. To.

Get the median value again in the narrowed list. This time the value in the center of the list is 2. Since this does not match the 2 of the search target, the search ends when it is determined that the target exists.

Comparison of calculated orders with regular search

In the normal search process, the search is performed to see if they match in order from the beginning. The calculation order is $ O (n) $ (however, if the value to be searched exists at the beginning, it will be less), and the larger the number of arrays ($ n $), the longer the linear processing time. It will become.

On the other hand, in the case of binary search, the calculation order is $ O (log_2 n) $, so even if the size of the array becomes large, the processing time will be bloated.

When can it be used

While a binary search is faster than a normal search, it can only be used with a sorted array for a binary search (unless it is sorted, the magnitude relationship will be strange when splitting the array. ).

Therefore, in the case where the array to be searched is not sorted and the search is executed only once, the calculation cost of sorting is higher than that of normal search, and the merit of using binary search is There is none.

On the other hand, if the array has already been sorted, or if the search process is repeated many times, the calculation cost can be kept lower by using the binary search even if the sort is executed.

Write it yourself in Python

You can use binary search for a list of characters as well as a numerical value, but this time we will proceed as a sample with a list that stores integers.

Also, instead of controlling to return the index of the search result, we will simply check whether the list contains values.

from typing import List

list_value: List[int] = [
    100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)



def binary_search(sorted_list: List[int], search_value: int) -> bool:
    """
Perform a binary search to see if the value to be searched is included in the list
Get the boolean value.

    Parameters
    ----------
    sorted_list : list of int
A list containing sorted integer values.
    search_value : int
The value to be searched.

    Returns
    -------
    value_exists : bool
Whether the value is included in the list.
    """
    left_index: int = 0
    right_index: int = len(sorted_list) - 1
    while left_index <= right_index:
        middle_index: int = (left_index + right_index) // 2
        middle_value: int = sorted_list[middle_index]

        if search_value < middle_value:
            right_index = middle_index - 1
            continue
        if search_value > middle_value:
            left_index = middle_index + 1
            continue

        return True

    return False

I will touch the chords in order.

First of all, in binary search, the target list needs to be sorted, so the sorted function is used to sort the list (the sort method etc. does not change).

list_value: List[int] = [
    100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)

Next is the processing of the binary search function.

    left_index: int = 0
    right_index: int = len(sorted_list) - 1

Variables for handling the index range of the target list are set as left_index and right_index. The leftmost index of the list is left_index and the rightmost index is right_index. These values are updated on one side each time they are bisected until the loop finishes the search.

    while left_index <= right_index:

The process of dividing into two is repeatedly executed in a while loop. This loop repeats as long as the leftmost index is to the left of the rightmost index or has the same intex. If it is to the right of the index at the right end, the range of the target list is exhausted (all targets have been searched), so the loop is terminated and it is judged that the target was not found. ..

        middle_index: int = (left_index + right_index) // 2
        middle_value: int = sorted_list[middle_index]

Inside the loop, middle_index stores the median value in the target array range. Divide by 2 by // 2 and truncate the fraction (//behaves like a floor in addition to division).

It also refers to that index as well as the center index and sets the center value to a variable (middle_value).

        if search_value < middle_value:
            right_index = middle_index - 1
            continue

In the if statement, if the value to be searched is smaller than the center value, the array is divided into only the left half, so the rightmost index (right_index) is set to the left of the center index (middle_index --1". ).

        if search_value > middle_value:
            left_index = middle_index + 1
            continue

On the other hand, if the value to be searched is larger than the center value, adjust the value of the leftmost index (left_index) so that the array is only the right half.

        return True

If the value to be searched is neither smaller nor larger than the median value, that is, if it is the same as the median value, True is returned as the value to be searched exists.

    return False

I will actually run it. First, try from the condition that the target exists in the list.

value_exists = binary_search(
    sorted_list=sorted_list,
    search_value=83)
print(value_exists)
True

True is returned normally. Next, try specifying the conditions that the search target is not included in the list.

value_exists = binary_search(
    sorted_list=sorted_list,
    search_value=84)
print(value_exists)
False

This is also False as expected.

References and reference sites

Recommended Posts

Write a binary search in Python
Write a depth-first search in Python
Binary search in Python
Binary search in Python (binary search)
Binary search in Python / C ++
Algorithm in Python (binary search)
Write A * (A-star) algorithm in Python
Create a binary file in Python
Write a pie chart in Python
Write a vim plugin in Python
Write the test in a python docstring
Algorithm in Python (ABC 146 C Binary Search
Write a short property definition in Python
Write a Caesar cipher program in Python
Write a simple greedy algorithm in Python
Write a simple Vim Plugin in Python 3
Write Python in MySQL
Binary search (python2.7) memo
[Python] Binary search ABC155D
Linear search in Python
Binary search with python
Binary search with Python3
Write Pandoc filters in Python
Create a function in Python
Create a dictionary in Python
Write beta distribution in Python
Write python in Rstudio (reticulate)
Search for strings in Python
Make a bookmarklet in Python
Draw a heart in Python
Write a super simple molecular dynamics program in python
I want to write in Python! (2) Let's write a test
Write a log-scale histogram on the x-axis in python
Algorithm in Python (breadth-first search, bfs)
Maybe in a python (original title: Maybe in Python)
How to write a Python class
Write a table-driven test in C
[python] Manage functions in a list
Hit a command in Python (Windows)
Implement a circular expression binary search in Python. There is a comparison with a simple full search.
Write JSON Schema in Python DSL
Save the binary file in Python
Create a DI Container in Python
Write an HTTP / 2 server in Python
Draw a scatterplot matrix in python
Write AWS Lambda function in Python
ABC166 in Python A ~ C problem
Algorithm in Python (depth-first search, dfs)
Write selenium test code in python
Solve ABC036 A ~ C in Python
Implementing a simple algorithm in Python 2
Create a Kubernetes Operator in Python
Solve ABC037 A ~ C in Python
Run a simple algorithm in Python
Draw a CNN diagram in Python
Create a random string in Python
Write C unit tests in Python
Schedule a Zoom meeting in Python
Depth-first search using stack in Python
Write a batch script with Python3.5 ~
When writing a program in Python