[PYTHON] Let's search for numerical values by linear search / 2-minute search

Hello. Thank you for your support m (_ _) m It's been almost three weeks since I started posting on September 23rd. It's fun in no time (laughs).

Well, this time it's a search. Let's start with a linear search. You don't have to be ready. 図1.PNG Just check if the value you are looking for matches the deficit in order from the left like this.

I'm sorry, the figure is cut off in the middle. .. Let's write it right away.

`linear_search.py`


def search(x,key):
    
    for i in range(len(x)):
        if x[i] == key:
            print(f"value is placed at x[{i}]")
            break
 #Final term x[6] !=For key, if x mentioned above[i] ==Because it passes the key
 #Enter the following if statement as it is.
 #i == len(x)-If it is 1, it is fail.
        if i == len(x)-1:
            print("fail to serch")
            break


if __name__ == "__main__":
    x = [6,4,3,2,1,2,8]                      #Specify an array
    key = int(input("enter search value: ")) #Enter the value you want to find
    search(x,key)

Next is a 2-minute search. The prerequisites for linear search are very different. I made the image of the difference. 図2.PNG In the case of linear search, we compare given things from the end, The 2-minute search doesn't go that way. Align once. Please note that the start is completely different. (? _ ?)(? _ ?)(?_?) Yes, I will go to the next step regardless. 図3.PNG If you are looking for ** 3 **, you can find it in one shot by comparing it with the median (laughs). But what if you're looking for a value less than 3? 図4.PNG What if the value you want to find is ** 1 **? If the median of [1, 2, 2] is not 2, then it is even less. Just look at x [0] where 1 is stored. If you still don't have the value you're looking for, you're looking for something in the first place It will not exist in the prepared array. Mendoia Argo is not good unless it is organized once, but it seems to be quite famous. This time I wrote it recursively.

`binary_search.py`


def binary_search(x,left,right,key):
    cen = (left + right)//2
    if left > right:
        print(f"left is {left},right is {right}")
        print("faile to search")
        return None
    if x[cen] == key:
        return print(f"found at x[{cen}]")

    #Median x[cen]Is greater than the search key
    if x[cen] > key:
        print(f"left is {left},cen is {cen}")
        binary_search(x,left,cen-1,key)#cen-One"-1"Is the miso!!!

    #Median x[cen]Is less than the search key
    if x[cen] < key:
        print(f"cen is {cen},right is {right}")
        binary_search(x,cen+1,right,key)#cen+One"+1"Is the miso!!!
    
if __name__ == "__main__":
    x =[1,2,2,3,4,6,8]
    
    binary_search(x,0,len(x)-1,1)

`Execution result.py`


left is 0,cen is 3
left is 0,cen is 1
found at x[0]

Select the left side and gradually narrow it. I tried to recreate the image by increasing the array length. This may be easier to understand (median red, ** if you're looking for 7 **). 図5.PNG What if you're not looking for ** 7 **? Please pay attention to the ** miso ** described below.

`miso.py`


    #Median x[cen]Is greater than the search key
    if x[cen] > key:
        print(f"left is {left},cen is {cen}")
        binary_search(x,left,cen-1,key)#cen-One"-1"Is the miso!!!

    #Median x[cen]Is less than the search key
    if x[cen] < key:
        print(f"cen is {cen},right is {right}")
        binary_search(x,cen+1,right,key)#cen+One"+1"Is the miso!!!

Just in case, when you run it, you will see the following comments.

`Execution result.py`


left is 5,right is 4 
faile to search

That's right. left> right is realized. What do you mean?

If you are looking for ** 6 ** Enter ** if x [cen]> key: ** in the description.

The result is ** binary_search (x, left, cen-1, key) **. At this point, left == right, so considering the above formula left> right, right ??. This is the mechanism of reversal. If you come this far, you can say that there is nothing, right? ??

The opposite pattern (if x [cen] <key :) is also true (≧ ▽ ≦)

If anyone can write it more simply We apologize for the inconvenience, but thank you for your understanding. m (_ _) m