정렬과 탐색(Sorting & Searching)

📍 sort

sorted() : python built-in function. 정렬된 새로운 리스트 생성
sort() : python list method. 해당 리스트 정렬

sorted(list, key=lambda x: len(x), reverse=True)  # 원소의 길이를 기준으로 역순 정렬하여 새로운 리스트 생성

---

📍 search

선형 탐색(linear search), 순차 탐색(sequential search) : 순차적으로 모든 요소 탐색. 최악의 경우 모든 요소 탐색. O(n)
이진 탐색(binary search) : 정렬된 배열에 사용. Divide & Conquer. O(logn)

---

binary search 구현

def binary_search(L, x):
    min = 0
    max = len(L) - 1
    
    while min <= max:
        mid = (min + max) // 2
        if L[mid] > x:
            max = mid - 1
        elif L[mid] < x:
            min = mid + 1
        else:
            return mid
    
    return -1

---

프로그래머스 - 어서와! 자료구조와 알고리즘은 처음이지? 강의를 듣고 정리한 내용
https://programmers.co.kr/learn/courses/57