Searching関連

binary_search.py

"""
 Binary Search
 - how you look up a word in dictionary or a contact in phone book.
 * Items have to be sorted!
"""


alist = ["Apple", "Banana", "Grapes",
         "Kiwi", "Mango", "Mangosteen",
         "Peach", "Pears", "Strawberry", "Watermelon"]


def binary_search(alist, target):
    low = 0
    high = len(alist)-1
    steps = 0

    while low <= high: # It's important in binary search.
        steps += 1
        mid = (low + high) // 2  # floor. Don't forget bracket when you computate.
        if alist[mid] == target:
            print("steps:", steps)
            return mid
        if alist[mid] < target:
            low = mid+1  # if just mid itself assigned to start, the range gose to convergence.
        else:
            high = mid-1 # if just mid itself assigned to start, the range gose to convergence.

    return -1


print(binary_search(alist, "Mango"))

lniear_search.py

"""
Returns the index of the target object from collection.
Return -1 if the target does not exist in the collection.
"""

alist = ["Apple", "Banana", "Grapes",
         "Kiwi", "Mango", "Mangosteen",
         "Peach", "Pears", "Strawberry", "Watermelon"]

def liearsearch(alist, target):

    steps = 0

    for i in range(len(alist)):
        steps += 1
        if target == alist[i]:
            print("steps:", steps)
            return i
    return -1

print(liearsearch(alist, "Mango"))
#steps: 5
#4