[What is an algorithm? Introduction to Search Algorithm] ~ Python ~

Overview

When I first started programming, I didn't know anything about algorithms. Merge sort? Binary search? Quick sort? It wasn't fun at all to face any code around the algorithm, and I didn't understand it at all.

But when I heard the word algorithm, I had a scary impression. I had a strong impression that it was difficult and could only be used by really smart programmers. What is an algorithm?

That's true, and I felt the same way. But only recently have I been able to deal with algorithms.

Any algorithm is designed to solve some ** problem **. I want to extract only one target data from the data containing 10,000 random numbers. I want to prevent the data from being eavesdropped on the way Our world has a lot of problems

And in such a case, the algorithm is very useful.

In understanding any algorithm, let's pay attention to the ** 2 points ** that we will introduce. Then you will find that the world of algorithms is not as harsh as you might think.

What is an algorithm?

An algorithm (English: algorithm [ˈælgəˌrɪðəm]) is a formalized representation of a procedure for solving a problem in mathematics, computing, linguistics, or related fields. Wikipedia

In other words, an algorithm is a procedure for solving a problem. In order to give a more detailed explanation, if we put out an algorithm that is familiar to us, ** Formula for finding the area of a circle ** This is also one of the finest algorithms

Speaking of a typical formula for finding the area of a circle,

Area of a circle = radius x radius x π

is not it. ** "I want to find the area of a circle quickly and as accurately as possible! When I run into the problem ** This algorithm was born in Greece long ago to solve this problem. This formula is a procedure for solving the problem of finding the area of a circle.

Isn't this a little lowering the threshold for the algorithm? To get a better understanding of the algorithm ■ ** What is the problem **, and ■ ** What is this algorithm solving? ** If you think about the above two points, your understanding will advance!

If the formula of the yen, I want to find the area of a circle quickly and as accurately as possible! The first problem was This algorithm can easily find the area of a circle as long as you include the radius of the circle.

Other algorithms can be thought of in the same way.

First of all, as a premise I have a problem An algorithm exists to solve it.

Let's do our best from here!

Algorithm type

This time, I will focus on two types of algorithms and explain them in the following order. ■ Search algorithm ■ Sort algorithm

Of course, there are many other algorithms However, these two are typical algorithms that appear in the questions of university class exams and information technology engineer exams.

Also, if you search for algorithm, the sort algorithm will be hit first, To understand the sorting algorithm, you must first understand the search algorithm before you can understand what the sorting algorithm exists for. So first learn the search algorithm and then the sort algorithm

Search algorithm

First, there is a search algorithm as an algorithm that you should remember. It sounds difficult at first glance, but it's very easy. An algorithm that finds the desired data from a huge data group It is called a search algorithm.

■ Linear search algorithm

First, let's imagine with playing cards 13 heart-shaped playing cards are randomly arranged from 1 to K. At this time, what would you do if you were asked "Please answer where the 7 playing cards of the heart are"?

Perhaps many would flip through the cards one at a time looking for a hard 7 playing card. In the world of algorithms, this is called a linear search algorithm (or sequential search algorithm). It is called sequential search because it turns straight one by one. It is called a linear search because it does not skip one sheet in the middle or start turning from the middle, but continues the search from the beginning to the end until the desired data is found.

It's easy to replace this with a program Just turn it with a for statement

linear_search.py



# coding: utf-8
# Here your code !


def linear_search(card_list, card):
    for i,element in enumerate(card_list):
        if element == card:
            print("{0}Second{1}There is".format(i+1,card))
            return
    print("{0}Was not".format(card))
    return
    
if __name__ == '__main__':
    heart_cards = ["h-5","h-J","h-2","h-9","h-1","h-7","h-K","h-4","h-10","h-3","h-6","h-8","h-Q"]
    heart_king = "h-K"
    linear_search(heart_cards,heart_king)

However, although this linear search algorithm is very simple and straightforward, it is often inefficient in real life situations. If the number of data is small like this time, there is no problem, but what if the data increases to 10,000, 100,000, 1 million? Isn't it a huge amount of time to check the data one by one?

Of the linear search list Maximum number of searches is N (N is the number of data) Average number of searches is N / 2 It will be. So, with a linear search algorithm, if you want to search 1 million pieces of data, you have to turn the cards up to 1 million times, and on average 500,000 times. It takes a lot of time

■ 2-minute search algorithm

Next, let's change the theme of playing cards This time, only 10 of the heart playing cards 1 to K are arranged in ascending order (always arranged in ascending order). At this time, what would you do if you were asked "Please answer where the 8 playing cards of the heart are"?

Do you want to do a linear search again?

No, in fact, we can only use more efficient algorithms if we have the condition that the data is sorted in ascending order. It is called a binary search algorithm.

First, turn over the middle playing card from the playing cards Then 6 came out The number of playing cards we want to find is 8 Since the playing cards are arranged in ascending order, you can see that the target playing card exists on the right side of this middle playing card. Now turn over the playing cards in the middle on the right side Then 10 will come out This time it is smaller than this so you can see that it is on the left side When I turned over the playing cards in the middle again, I found it safely.

In other words, binary search (also called binary search) is an algorithm that finds the desired data by halving the sorted elements and comparing whether the desired data is in front or behind. Let's replace it with a program

binary_search.py


# coding: utf-8
# Here your code !

def binary_search(card_list, card):
    low = 0
    high = len(card_list) - 1
    print(high)
    while low <= high:
        mid = (low + high) // 2
        #print(mid)
        #print(card_list[mid])
        if card_list[mid] == card:
            print("{0}Second{1}There is".format(mid,card))
            return
        elif card_list[mid] < card:
            low = mid + 1
        else:
            high = mid - 1
    return

if __name__ == '__main__':
    heart_cards = [1,2,4,5,6,8,9,10,12,13]
    heart_eight = 8
    binary_search(heart_cards, heart_eight)

The maximum number of searches in the linear search list is N (N is the number of data), and the average number of searches is N / 2. It was. On the other hand, the binary search algorithm Maximum number of searches is log2N + 1 The average number of searches is log2N Will be

In other words, when searching for 1 million pieces of data with the 2-minute search algorithm, it is only necessary to turn the Trump 21 times at the maximum and 20 times on average. Look back at the time when you were flipping cards up to 1 million times during the search algorithm. It's much more efficient than when doing a linear search.

[Calculation site useful for daily life and practice] Logarithmic function

However, as I explained at the beginning, this 2-minute search algorithm cannot be used unless the data is always aligned! If you can understand this far, it's natural. This two-minute search algorithm is valid because there is a condition that the data is always the smallest on the left side and larger on the right side.

However, in reality, the data in the world is rarely aligned by nature.

So what should I do?

The sort algorithm comes into play in such a case.

The sorting algorithm is an algorithm that sorts randomly and irregularly arranged data groups in ascending order, descending order, and so on.

■ Summary of search algorithms

This is the end of the explanation of the search algorithm.

"I want to get some desired data from the data group! When there was a problem We can use a linear search algorithm This is a simple, straightforward algorithm that even beginners can solve this problem.

However, this linear search algorithm has another problem. That it is inefficient This algorithm has the potential to search 1 million times for 1 million pieces of data.

And the solution to this problem is the 2-minute search algorithm.

"I want to efficiently obtain data of a certain purpose from the data group! ], You can use this 2-minute search algorithm.

But again, this two-minute search algorithm has another problem. That is, it cannot be used unless the data is aligned. This two-minute search algorithm can be used because it is assumed that the data are sorted in ascending and descending order.

And the sorting algorithm that will be introduced later solves this problem. There are actually many types of this sorting algorithm. Depending on each, the efficiency may differ or they may be used in combination.

However, each sorting algorithm has one purpose.

Aligning disjointed data groups

Let's start from the next


Also for other search algorithms Hash search algorithm There is something called. I will omit it this time I hope I can introduce you somewhere again


reference

[[Paiza development diary] List of algorithm types that IT engineers should know, which cannot be heard now](http://paiza.hatenablog.com/entry/2015/10/19/IT%E3%82%A8%E3 % 83% B3% E3% 82% B8% E3% 83% 8B% E3% 82% A2% E3% 81% AA% E3% 82% 89% E7% 9F% A5% E3% 81% A3% E3% 81 % A6% E3% 81% 8A% E3% 81% 8D% E3% 81% 9F% E3% 81% 84% E3% 80% 81% E4% BB% 8A% E6% 9B% B4% E8% 81% 9E % E3% 81% 91% E3% 81% AA% E3% 81% 84% E3% 82% A2)

Recommended Posts

[What is an algorithm? Introduction to Search Algorithm] ~ Python ~
[Introduction to Udemy Python 3 + Application] 54. What is Docstrings?
An introduction to Python Programming
[Ruby / Python / Java / Swift / JS] What is an algorithm?
Python> What is an extended slice?
An introduction to Python for non-engineers
[Python Tutorial] An Easy Introduction to Python
What is python
What is Python
An introduction to Python for machine learning
An introduction to Python for C programmers
[Introduction to Python] What is the most powerful programming language now?
[Introduction to Python] What is the difference between a list and a tuple?
[Python] What is Pipeline ...
Introduction to Python language
Introduction to OpenCV (python)-(2)
[Python] What to do when an error related to SSL authentication is returned
Introduction to Python "Re" 1 Building an execution environment
[Introduction to Algorithm] Find the shortest path [Python3]
What is an iterator?
[Introduction to Python] What is the method of repeating with the continue statement?
[Python] What is virtualenv
An introduction to Python distributed parallel processing with Ray
Reading Note: An Introduction to Data Analysis with Python
Introduction to dictionary lookup algorithm
Introduction to Python Django (2) Win
An introduction to private TensorFlow
An introduction to machine learning
Python is an adult language
What is an instance variable?
Search algorithm using word2vec [python]
Introduction to serial communication [Python]
Algorithm in Python (binary search)
[Python] Python and security-① What is Python?
[Python] * args ** What is kwrgs?
[Introduction to Python] <list> [edit: 2020/02/22]
Introduction to Python (Python version APG4b)
An introduction to Bayesian optimization
Introduction to Python For, While
What is a python map?
Python Basic Course (1 What is Python)
[Python] Type Error:'WebElement' object is not iterable What to do when an error occurs
[Introduction to Python] What is the recommended way to install pip, a package management system?
[Introduction to Python] What is the important "if __name__ =='__main__':" when dealing with modules?
An introduction to Python that even monkeys can understand (Part 3)
Introduction to Python scikit-learn, matplotlib, single-layer algorithm (~ towards B3 ~ part3)
An introduction to Python that even monkeys can understand (Part 1)
An introduction to Python that even monkeys can understand (Part 2)
What is Python? What is it used for?
Algorithm in Python (breadth-first search, bfs)
[Python] What is a zip function?
[Python] What is a with statement?
[Introduction to Udemy Python 3 + Application] 58. Lambda
[Introduction to Udemy Python 3 + Application] 31. Comments
Introduction to Python Numerical Library NumPy
An introduction to Mercurial for non-engineers
Practice! !! Introduction to Python (Type Hints)
[Introduction to Python3 Day 1] Programming and Python
[Introduction to Python] <numpy ndarray> [edit: 2020/02/22]
[Introduction to Udemy Python 3 + Application] 57. Decorator
Introduction to Python Hands On Part 1