TIL_3 | algorithm - Binary Search, 쉽다 쉬워!

이진탐색(Binary Search) 알고리즘은 빠른 시간 복잡도(O(logN))를 가졌고, 생각보다 쉽기 때문에 기분이 좋은(?) 알고리즘이다!🙌

data = [1, 3, 4, 6, 7, 8, 10, 13, 14]
goal = 4

만약 input 값이 위와 같이 주어진다면 이진탐색은 아래의 그림과 같이 풀어 나갈 수 있다.

위의 그림(참조)과 같이 이진탐색 알고리즘의 가장 큰 특징은 '범위의 중간값보다 크거나 작을때 값이 포함되지 않는 부분은 버리는 것'이다. 계속해서 버리다 보면 목표 값을 빠른시간만에 찾을 수 있다.

준비사항? (feat. mid, lp, rp)

이진탐색 알고리즘를 사용하기 위해서는 몇개의 준비과정이 필요하다.

lp = 0
rp = max(data)
while lp <= rp:
	mid = (lp + rp) // 2
    if data[mid] > goal:
    	rp = mid - 1
    elif data[mid] < goal:
    	lp = mid + 1
    else:
    	print(mid)
    	break

lp(left point), rp(right point), mid(중간값)이다. lp는 가장 작은 값(0)으로 시작하여 점점 증가되는 값이고, rp는 가장 큰 값(max(data))으로 시작하여 점점 작아지는 값이다. mid는 이것들의 중간값으로 세가지 변수 다 가변적이다.

while문으로 반복하면서 data[mid]의 값과 goal의 값을 비교하여 두 지점중 하나를 변경해준다.

첫번째 if문은 goal이 mid의 값보다 작다면 범위의 왼쪽에 위치한다는 뜻이니 rt의 값을 mid -1 값으로 설정한다.(data[mid]값보다도 작다는 뜻이니 mid -1을 해야한다.)

같은 원리로 두번째 if문은 goal이 mid의 값보다 크다는 뜻이니 mid +1을 설정한다.

else문은 data[mid]가 곧 goal이라는 뜻이니 print하고 break한다.

Today, Learned

배운점

• 이진탐색에 필요한 준비물(mid, lp, rp)의 개념을 이해했다.
• data의 범위 조건이 1 ~ 10,000이라면 rp의 값을 10,000을 설정했는데, max(data)로 설정하면 된다는 점!!

느낀점

• 결정 알고리즘까지 풀었는데, 쉽다고 방심하면 안되는것..(응욕문제..😱)
• 다른 알고리즘 개념보다 훨씬 쉬워서 힐링 + 꿀 + 피톤치드 문제라는 것!

오늘의 한마디

매일을 오늘같이. 아니, 오늘 = 오늘 X 1.2 만큼씩 성장해 나가자!🙏