이분 탐색

백준의 실버4 문제인 수 찾기를 풀다가 시간초과, 메모리 초과 다 경험해봤다.

꼼수로 풀려고 하면 이렇게 됨

이 문제를 풀려고 한 꼼수를 써본다. 약간 다시는 안 그래야겠다 생각해서..

1) if elem in m_array:

당연히 n!으로 푸니까 안 될듯

2) 테이블 만들어 두고 index로 찾을까?

문제는 들어오는 수가 2^-31 ~ 2^31이다. 128MB로는 해결 못 하는 크기다

3) 이분 탐색

놀랍게도 O(logN)이다. 로직도 간단한 편이라 항상 까먹는데 기억해야겠다.

lt = 0
rt = n -1

while lt <= rt:
	# 중간값을 설정
	mid = (lt + rt) // 2

	if num == n_arr[mid]:
		break
	
	elif num > n_arr[mid]:
		lt = mid + 1
	else:
    	rt = mid - 1