TIL-068 | 이진 탐색(Binary Search)

🌈 이진 탐색(Binary Search)

이진 탐색이란?

• 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

• 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 n과 비교한다. n이 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

• 반복문 혹은 재귀용법을 사용해서 구현할 수 있다.

이진 탐색의 장점

• 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

이진 탐색의 단점

• 검색 원리상 반드시 정렬된 리스트에만 사용할 수 있다

이진 탐색의 성능

• 데이터 집합의 크기를 n으로 두고 반복 횟수를 k라고 하면 아래와 같은 수식이 된다.
  
• 따라서 k=log2n 가 되고, 시간복잡도는 O(logn)이 된다.

이진 탐색의 구현

# 반복문
def binary_search(list):
    left = 0
    right = len(list)-1

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

    return mid

# 재귀함수
def binary_search_recursion(target, start, end, list):
	if start > end:
    	return None
    mid = (start + end) // 2
    
    if list[mid] == target:
    	return mid
    elif list[mid] > target:
    	end = mid - 1
    else:
    	start = mid + 1
        
    return binary_search_recursion(target, start, end, list)

완전 탐색(Bruto Force) 이란 ?

• 컴퓨터의 성능을 이용하여 가능한 모든 경우의 수를 탐색하는 방법

• 효율성 관점에선 최악의 방법이나 무조건 원하는 값을 탐색할 수 있다는 장점

완전 탐색의 구현

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

📝 Reference

1. https://cjh5414.github.io/binary-search/
2. https://duri1994.github.io/algorithm/algorithm-brutoforce-binarysearch/
3. https://yoongrammer.tistory.com/75