Binary search with Python3

Classroom & attention

Since the binary search was written in the algorithm class, it was implemented in Python3. Since the array below is destroyed (erasing elements), it is better to copy the data and execute it when actually using it, or change the conditions using variables such as left and right. so. I thought it would be more convenient to make it a function, but Python can be searched using in, and I just coded it in the practice of the algorithm, so it's done well, yes.

Source description

Prepare an appropriate list and sort it in ascending order. Store the number you want to find in sa_num. Use cnt to count how many times it has been processed during the search. end is used as an end condition and suc is used as a flag for success. Repeat if end is 0 If the element is 1, it is finished if only that element is examined, so flag it as end = 1. If not, get the median. If the median and the value you want to find do not match, compare the size of the median and the value you want to find. If the median is larger, the value you want to find is from 0 to index, so you don't need the right side of the array (from index to the end), so delete it using a slice. On the contrary, if it is smaller than the median, the left side is deleted. If the number of elements in the array becomes 1, take out the elements and compare them with the numerical value you want to find. If you can't find the number you're looking for, you're done.


lis = [15,23,25,601,65,87,9,103,15,30,11,13]
lis.sort()

sa_num = 25

cnt = 0
end = 0
suc = 0

while end == 0:

    cnt += 1

    print(lis)

    if len(lis) != 1:

        index = int(len(lis) / 2)

        if lis[index] == sa_num:

            print('suc' + str(sa_num))
            end = 1

        elif lis[index] > sa_num:

            del lis[index:]

        elif lis[index] < sa_num:

            del lis[0:index]

    else:

        if lis[0] == sa_num:

            print(sa_num)
            end = 1

        else:

            print('Could not be located.')
            suc = 1
            end = 1

if suc != 1:

    print(str(cnt) + 'Found in the second search.')

else:

    print(str(cnt) + 'I searched several times but could not find it.')


Recommended Posts

Binary search with python
Binary search with Python3
Sequential search with Python
Binary search in Python
Binary search (python2.7) memo
[Python] Binary search ABC155D
Binary search in Python (binary search)
Algorithm learned with Python 10th: Binary search
Binary search in Python / C ++
Algorithm in Python (binary search)
Full bit search with Python
Search engine work with python
Search twitter tweets with python
Streamline web search with python
Write a binary search in Python
Learn search with Python # 2bit search, permutation search
FizzBuzz with Python3
Scraping with Python
Statistics with python
Scraping with Python
Python with Go
Twilio with Python
Play with 2016-Python
visualize binary search
Tested with Python
ABC146C (binary search)
with syntax (Python)
Bingo with python
Zundokokiyoshi with python
Excel with Python
Microcomputer with Python
Cast with python
Algorithm learned with Python 9th: Linear search
Try working with binary data in Python
Algorithm in Python (ABC 146 C Binary Search
Search the maze with the python A * algorithm
Algorithm learned with Python 12th: Maze search
Serial communication with Python
Zip, unzip with python
Django 1.11 started with Python3.6
Primality test with Python
Python with eclipse + PyDev.
Socket communication with Python
Data analysis with python 2
Scraping with Python (preparation)
Try scraping with Python.
Csv output from Google search with [Python]! 【Easy】
Automatically search and download YouTube videos with Python
Learning Python with ChemTHEATER 03
"Object-oriented" learning with python
Run Python with VBA
Handling yaml with python
Solve AtCoder 167 with python
Serial communication with python
[Python] Use JSON with Python
Learning Python with ChemTHEATER 05-1
Learn Python with ChemTHEATER
Causal reasoning and causal search with Python (for beginners)
1.1 Getting Started with Python
Python Exercise 1-Breadth-first search
Binarization with OpenCV / Python