[python/자료구조] 탐색( 완전탐색 / 이분탐색 )

탐색이란?

---

많은 데이터 속에서 원하는 데이터를 찾는 것

탐색의 종류

---

• 완전탐색
• 이분탐색
• 깊이우선 탐색
• 너비우선 탐색
• 문자열 탐색
• KMP
• BM

---

1. 완전탐색

- 브루트 포스라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색,
  효율성 관점에서 최악의 방법

1-1. 반복문

 
def solution(trump):
    for i in range(len(trump)):
    if trump[i] == 8 :
        return i
    return -1
     

1-2. 재귀함수(동적계획법, 백트래킹, 탐욕법)
 - 무한루프에 빠질 수 있음에 주의!

 
def solution(trump, loc):
    if trump[loc] == 8 :
        return loc
    else :
        return solution(trump, loc+1)
         

2. 이분탐색

- 이진검색이라고도 하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘,
  중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 방법으로 left, mid, right를 사용하여 조정한다.

  
def solution(trump):
    left = 0
    right = len(trump)-1

    # left가 right보다 작거나 같다면
    while(left<=right):
        mid = (left+right) // 2  # mid 값 계산
    if trump[mid] == 8:
        return mid  # 정답일 경우 정답 반환
    elif trump[mid] < 8:
        left = mid + 1  # 정답보다 작을 경우 left를 mid+1로 이동
    elif trump[mid] > 8:
        right = mid -1  # 정답보다 클 경우 right를 mid-1로 이동

    return mid