[ALGORITHM] Binary Search (이진 탐색)

지난 며칠 간 인터뷰 준비를 하면서 릿코드를 푸는데 내가 CS 기초 알고리즘조차 다 까먹어버렸다는 좌절에 휩싸여 처음부터 다시 알고리즘 공부를 시작했다 🥺

잔말 말고, 오늘은 Microsoft Onsite 인터뷰에서 가장 많이 나온다는 알고리즘 중 하나인 Binary Search (이진 탐색) 에 대해 적어보며 혼자 다시 한번 더 정리해보고자 한다.

---

📖 Binary Search

• Binary Search is the most fundamental and useful algorithm in Computer Sciece
• It is the process of searching for a specific value in an ordered collection
• Binary Search should be considered every time you need to search for an index or element in a collection

3 PARTS OF SUCCESSFUL BS
1. Pre-processing: Sorting collection if is not
2. Binary Searh: Using a loop or recursion to divide search space in half after each comparison
3. Post-processing: Determine viable candidates in the remaining space.

---

❓Why Binary Search

(cred: GeeksforGeeks)

위 Array에서 element 23을 찾는다고 가정해보자.
그럼 룹을 돌려서 인덱스 값이 23과 맞을 때, 리턴 해주면 되는 간단한 문제를 왜 굳이 더 공부해가며 이딴 알고리즘을 써야할까? 🤬

Array에서 룹을 돌린다고 생각했을 때, 23은 인덱스 5에 위치해있기 때문에 룹을 여섯번 돌려야 값을 찾을 수 있다.

그렇다면 이진탐색을 사용했을 때를 생각해보면...

맨 왼쪽과 오른쪽 pointers를 각각 left (0), right (len(lst) - 1) 으로 둔다고 쳤을 때, 중간 값.
즉, (left + right) // 2 의 값보다 찾아야 하는 23의 값이 클 때, 작을 때의 케이스를 구분해서 two pointers의 범위를 좁혀가며 나머지 elements 를 걸러내는 방식으로 진행이 되기 때문에 훨씬 더 빠르게 찾고자 하는 값을 찾을 수 있다.

---

💻 코딩을 해보자

Binary Search 알고리즘의 원리를 활용해 코딩를 구현해보겠다 🥲
아래 코드는 찾고자 하는 값의 인덱스를 구하는 코드다.

def binary_search(lst, valToFind):
	left, right = 0, len(lst) - 1	# setting two pointers
    
    while left <= right:	# 범위가 cross 되기 전까지: negation이 되면 lst 안에 찾고자 하는 값이 없다는 뜻
    	midPoint = (left + right) // 2	# left와 right이 업데이트 될 때마다 새로운 중간값을 설정
        if lst[midPoint] == valToFind:	# 중간값과 찾아야 할 값이 같을 때 -> midPoint 리턴
        	return midPoint
         # 중간값보다 찾는 값이 더 클 때 
         # -> 찾아야 하는 값이 중간 기준 오른쪽에 있다는 뜻으로 left pointer 의 범위 좁히기
        elif lst[midPoint] < valToFind:	
        	left = midPoint + 1
         # 중간값보다 찾는 값이 더 작 때 
         # -> 찾아야 하는 값이 중간 기준 왼쪽에 있다는 뜻으로 right pointer 의 범위 좁히기
        else:
        	right = midPoint - 1
            
    return -1	# left > right -> 찾는 값이 lst안에 없음: -1 리턴

---

📍 정리

물론 Array에서 특정 값을 찾을 때, 해쉬맵이나 룹을 사용해 찾는 것도 좋지만, 그럴 경우에 대부분 TC: O(n) 을 깔고 가기 때문에 모든 value를 찾지 않아도 되는 이진 탐색이 (익숙해지기만하면;;) TC나 SC 부분에서 훨씬 깔끔하고 나은 것 같다.

Binary Search의 시간 복잡도는 O(logn)이고, Space Complexity는 O(1)이 된다.
따라서 인터뷰를 볼 때, 이런 비스무리한 문제가 나오면 BS사용을 고려해보자!... ㅈㅔㅂㅏㄹ

다음 포스트는 Binary Search에서 나온 Binary Search 'Tree' (이진탐색트리..)에 대해 적어보겠다. 🤓 👩🏻‍💻