[PYTHON] You will be an engineer in 100 days ――Day 61 ――Programming ――About exploration

Click here until yesterday

About exploration

Search in programming is to find the desired data.

There are various forms of data and how to search for data.

Linear search

When data is stored in list, in order from the beginning of the list If you look to the end of the list, you will find the data you want.

Such a search method is called linear search. It's simple and easy to implement because you only need to check in order.

The following example is a simple linear search example.

data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
target = 4559
flg = False

##Example of linear search
def linear_search(data, val):
    for x in data:
        if x == val:
            return True
    return False

print(linear_search(data, target))

True

I think it's a relatively easy-to-understand algorithm It will be difficult if there is more data that needs to be examined until all the values are found.

I'm looking for numbers in order from the top of the list, but if it's at the back of the list It will take a long time.

Average number of comparisons for $ \ frac {n + 1} {2} $ In the worst case, it will be $ O (n) $ processing.

Binary search

Considering how to find out quickly even if the number of data increases in the list Linear search is difficult.

When you look at a certain value, such as a dictionary or phone book, the desired value is higher than that. As a way to judge whether it is big or small A method to search at high speed by repeating the operation of narrowing down the search range to half It is called binary search.

#Binary search example
def binary_search(data, num):
    left , right = 0 , len(data) - 1
    while left <= right:
        m = (left + right) // 2
        if data[m] == num:
            return m
        elif data[m] < num:
            left = m + 1
        else:
            right = m - 1
    return -1

data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
data.sort()
print(data)
print(binary_search(data, 5119))

The data must be sorted to allow binary search. Sort the data before searching.

Breadth search

Not when searching for data stored in a list Suppose you want to find the desired data in the data that has a hierarchical structure.

For example, from data with a tree-like structure such as a website When finding the desired page At that time, breadth-first search and depth-first search can be considered.

Breadth first search

How to list things close to where you start your search and scrutinize each one It is called breadth-first search (BFS).

# BFS(Breadth-first search)
import os
from collections import deque
 
def bfs(path):
    q = deque([])
    q.append(path)
    while len(q) > 0:
        p = q.popleft()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path)
    return q

print(bfs('./'))

Depth first search

For breadth-first search, how to proceed as far as you want and return when you can't. It is called depth-first search (DFS).

Also known as the backtrack method.

import os
from collections import deque
 
def dfs(path):
    q = deque([]) 
    q.append(path)
    while len(q) > 0:
        p = q.pop()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path) 
    return q

print(dfs('./'))

Summary

A wide variety of data search methods The amount of calculation and execution speed will change greatly depending on how to assemble and search the data.

With the optimum data format according to the data to be handled Consider the exploration algorithm.

39 days until you become an engineer

Author information

Otsu py's HP: http://www.otupy.net/

Youtube： https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter： https://twitter.com/otupython