자료구조와 알고리즘3

배열 더 알아보기 : 정렬과 탐색(sort&searching)

3.정렬(Sort), 탐색(Search)

python 리스트의 정렬
(1) sorted(list)

• 파이썬 내장함수 (Built-in function)
• 정렬된 새로운 리스트를 얻어냄

(2)list.sort()

• 리스트의 매서드 (method)
• 해당 리스트를 정렬함

정렬의 순서를 반대로 (내림차순 정렬 reverse = True)

• list2 = sorted(list,reverse = True)
• list.sort(reverse = True)

정렬 - 문자열로 이루어진 리스트의 경우
정렬순서는 아스키코드의 순서를 따른다
(문자열의 길이가 긴것이 더 큰것이 아님)

정렬 - key옵션에 람다(lambda)표현식을 이용하여 정렬가능
추후 람다 표현식에 대해 서술하겠음

탐색 알고리즘(1) - 선형탐색(Linear Sesrch)
순차적으로 하나하나 탐색하는 방식
리스트의 길이에 비례하는 시간소요 O(n)
최악의 경우 : 모든 원소를 다 탐색해 보아야함

탐색 알고리즘(2) - 이진탐색(Binary Search)
업다운 게임의 형식으로 탐색하는 방법
탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용가능
크기순으로 정렬되어 있다는 성질을 이용
한번의 비교가 일어날 때 마다 리스트가 반씩 줄어들음(divide & conquer)
시간복잡도 O(log n)

3강 실습

이진 탐색 코드를 구현하라 (L에 x가 존재하지 않으면 -1을 리턴하라)

def solution(L, x):
    low = 0
    high = (len(L)-1)
    while low <= high:
        mid = (high + low) // 2
        if L[mid] == x:
            return mid
        elif L[mid] < x:
            low = mid+1
        else:
            high = mid-1
    return -1