[알고리즘] 문제2 - 탐색 알고리즘

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다.

 

선형 탐색 알고리즘 : 리스트의 처음부터 끝까지 순서대로 처음부터 하나씩 탐색하여 값을 찾는 것

이진 탐색 알고리즘 : 정렬된 리스트를 반씩 나누어 검색하여 값을 찾는 것 

---

 

 1 . 선형 탐색(Linear Serch)알고리즘 구현해보기

 

 조건 

-함수명 : linear_search

-매개변수명 : 탐색할 값(element), 받을 리스트(some_list)

-반환값 : element가 있을 경우 some_list의 인데스 반환, 없으면 None 반환

-for문 사용, element in some_list 사용 금지

---

풀이

# 시간 복잡도 : O(n)

def linear_search(element, some_list):
    for i in range(len(some_list)):
        if element == some_list[i]:
            return i

    return None


# 테스트
print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

 

'''
더 알아보기
'''

# element in some_list 사용 시

def linear_search(element, some_list):
    if element in some_list:
        return some_list.index(element)

    return None

# 배열명.index(x) : i가 배열에서 x가 처음 나타나는 인덱스가 되도록 가장 작은 i를 반환

 

 

---

 

 

 2. 이진 탐색(Binary Serch)알고리즘 구현해보기 

 

 조건 

-함수명 : binary_search

-매개변수명 : 탐색할 값(element), 받을 리스트(some_list)

-반환값 : element가 있을 경우 some_list의 인데스 반환, 없으면 None 반환

---

풀이

# 시간 복잡도 : O(lg n)

def binary_search(element, some_list):
    start = 0
    end = len(some_list)-1
    index = 1

    while start <= end:
        index = (start + end) // 2

        if element == some_list[index]:
            return index
        elif element < some_list[index]:
            end = index-1
        else:
            start = index+1

    return None


# 테스트
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))