탐색 (선형 / 이진 / 이진트리)

def linear_search(list, find_key):
    for i in range(len(list)):
        if list[i] == find_key:
            return i
    return "not find"


def binary_search(list, find_key):
    mid = len(list)//2
    while True:
        if list[mid] == find_key:
            return mid
        elif list[mid] < find_key:
            mid += mid/2
            if mid >= len(list):
                mid = len(list)-1
        else:
            mid -= mid/2
            if mid/2 == 0:
                mid = 0


class binary_tree:
    value = 0
    left = None
    right = None

    def __init__(self, value):
        self.value = value

    def get_value(self):
        return self.value

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

    def input_value(self, value):
        if self.value > value:
            if self.left is None:
                new_binary_tree = binary_tree(value)
                self.left = new_binary_tree
                return self.left
            else:
                return True
        else:
            if self.right is None:
                new_binary_tree = binary_tree(value)
                self.right = new_binary_tree
                return self.right
            else:
                return False


def binary_tree_create(list):
    root = binary_tree(list[0])
    for i in range(len(list)):
        if list[i] != root.get_value():
            now_obj = root
            while True:
                temp_obj = now_obj.input_value(list[i])
                if isinstance(temp_obj, binary_tree):
                    break
                else:
                    if temp_obj is True:
                        now_obj = now_obj.get_left()
                    else:
                        now_obj = now_obj.get_right()

    return root


def binary_tree_search(node, value, depth):

    temp_value = node.get_value()
    if temp_value == value:
        return temp_value, depth
    elif temp_value > value:
        if isinstance(node.get_left(), binary_tree) is False:
            return "not find"
        return binary_tree_search(node.get_left(), value, depth+1)
    else:
        if isinstance(node.get_right(), binary_tree) is False:
            return "not find"
        return binary_tree_search(node.get_right(), value, depth+1)


temp_list = [33, 11, 99, 1, 22, 88, 55, 44, 66, 77]


print(linear_search(temp_list, 77))
print(binary_search(temp_list, 77))
root = binary_tree_create(temp_list)
print(binary_tree_search(root, 77, 0))

이진트리는 트리 형식으로 만들어야 함으로 쪼금 길다.

선형 탐색 O(n)

이진 탐색 O( logn) 단 정렬이 되 있어야 함

이진 트리 O( logn)