3강: 정렬(Sort), 탐색(Search)

강의

"정렬" 내장 함수는 2가지 종류가 있습니다.

• sorted() : 정렬된 새로운 리스트
• sort() : 기존의 리스트 정렬

 

옵션을 이용해 다양한 기준으로 정렬할 수 있습니다.

• reverse : 역순

 

원소가 문자열인 경우 사전 순서에 따라 정렬합니다.

원하는 키를 지정하여 정렬의 기준을 설정할 수 있습니다.

 

"탐색" 알고리즘은 선형 탐색과 이진 탐색이 있습니다.

• 선형 탐색 : O(n)
• 이진 탐색 : O(log n)

정렬이 되어 있거나 리스트의 크기가 큰 경우에는 선형 탐색보다 이진 탐색이 더 유리합니다.

 

 

3강 실습: 이진 탐색 구현해보기

⭐ 직관적 풀이 : 리스트에 찾으려는 원소가 존재하는지 여부를 우선 확인한 후, index() 함수를 이용하는 방법!

def solution(L, x):
    if x not in L:
        return -1
    else:
        return L.index(x)

→ 시간 초과 : 선형 탐색으로 작성된 코드

 

 

 

 

 

 

⭐ 힌트 풀이 : 이진 탐색을 이용하는 방법!

def solution(L, x):
    start = 0
    end = len(L)
    
    idx = 0
    
    while 0 <= idx < len(L) and end-start > 1:
        l = int((end-start)/2)
        
        idx = start + l
        
        if L[idx] == x:
            return idx
        elif L[idx] < x:
            start = idx
        else:
            end = idx

    return -1