선형탐색, 이진탐색(python)

탐색

---

선형탐색 또는 순차탐색

• 리스트의 앞에서부터 뒤로 하나씩 조사하면서 값을 탐색
• 리스트의 마지막 인덱스보다 i가 작으면서 리스트의 i방 값이 찾고자 하는 값이 아니면 계속 1을 증가시킨다.  찾고자 하는 값이면 그냥 바로 나와서 그 인덱스를 리턴해준다. 
  찾고자 하는 값이 리스트 안에 없다면 i는 리스트의 길이와 같아지므로 -1을 리턴한다.(원하는 값이 없다.)
• 리스트의 길이에 비례하는 시간이 소요됨
• 시간복잡도 : O(n)

def linear_search(L, x):
    i = 0
    while i < len(L) and L[i] != x:
        i+=1
    if i < len(L):
        return i
    else:
        return -1

 

 

이진 탐색

• 탐색하려는 리스트가 정렬되어있을 때만 적용 가능
• 맨 처음, 맨 마지막의 중간 인덱스 값을 기준으로 중간 인덱스의 값이 찾으려는 값보다 작으면 맨 처음 인덱스를 중간 인덱스+1로, 찾으려는 값보다 크면 맨 마지막 인덱스를 중간 인덱스-1로,,,
• 한 번 비교가 일어날 때마가 리스트를 반씩 줄인다.
• 시간복잡도 : O(log n)

def binary_search(L, x):
    res = -1
    upper = len(L)-1
    lower = 0
    while lower <= upper:
        middle = (lower+upper) // 2
        if L[middle] > x:
            upper = middle-1
        elif L[middle] < x:
            lower = middle+1
        elif L[middle] == x:
            res = middle
            break

    return res

 

 

ps. 이진 탐색은 다음에 더 알아봐야겠어요!

 

오류가 있다면 알려주시면 감사하겠습니다!

---