Binary search in Python (binary search)

This is Qiita's first post.

This time, I implemented binary search in two patterns, loop and recursion.

Binary search in loop

binary_search_loop.py


from typing import List


def binary_search_loop(data: List[int], target: int) -> int:
    left, right = 0, len(data)

    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return None


if __name__ == "__main__":
    data: List[int] = [int(x) for x in input("Sorted array(Space delimited)Enter: ").split()] #I used the inclusion notation
    target = int(input("Enter target: "))

    result = binary_search_loop(data, target)
    if result is not None:
        print(f"found: {result}Was second")
    else:
        print("not found")

Recursive binary search

binary_search_recursion.py


from typing import List


def binary_search_recursion(data: List[int], target: int) -> int:
    def recursion(left=0, right=len(data) - 1):
        if left > right:
            return None

        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            return recursion(mid + 1, right)
        else:
            return recursion(left, mid - 1)

    return recursion()


if __name__ == "__main__":
    data: List[int] = list(map(int, input("Sorted array(Space delimited)Enter: ").split())) #Using map
    target = int(input("Enter target: "))

    result = binary_search_recursion(data, target)
    if result is not None:
        print(f"found: {result}Was second")
    else:
        print("not found")

What I noticed

--Since the data obtained by input () is str type, convert it to int type. --If it is still str type, it will be compared by character code instead of number in comparison.

Recommended Posts

Binary search in Python
Binary search in Python (binary search)
Binary search in Python / C ++
Binary search (python2.7) memo
[Python] Binary search ABC155D
Linear search in Python
Binary search with python
Binary search with Python3
Algorithm in Python (ABC 146 C Binary Search
Search for strings in Python
Algorithm in Python (breadth-first search, bfs)
Save the binary file in Python
Create a binary file in Python
Algorithm in Python (depth-first search, dfs)
Write a depth-first search 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
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
visualize binary search
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
ABC146C (binary search)
Lifegame in Python.
FizzBuzz in Python
StepAIC in Python
N-gram in python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Algorithm learned with Python 10th: Binary search
Try working with binary data in Python
Search and play YouTube videos in Python
In search of the fastest FizzBuzz in Python