[Algorithm]숫자 맞추기 게임 이진 탐색 알고리즘

2021.05.07 - [분류 전체보기] - [coding_test] 순위 검색

[coding_test] 순위 검색

코딩테스트를 하다 알게된 알고리즘인데.. 

나 사실 알고리즘이 뭔지 모른다... 정말 많이 들어봤지만

위키백과

이진 탐색( binary search ) : 

술 먹을 때 숫자 업다운 게임할 때 맨날 사용했는데 이게 알고리즘이였다.. 

이것을 공식화 한것이 이진탐색이다!

 

주의 해야할 것은

정렬되어 있는 데이터에서 탐색이 가능하다.

 

크기가 n인 리스트 data에서 target 이라는 특정 요소를 찾아낸다고 가정했을 때,

# 1.low = 00, high = n−1 로 초기화 합니다.
def binary_search(data, target, low, high): 
	if low > high: 
    	return false 
    else: 
    	# 2. mid 는 (log + high) 를 2 로 나눈 몫으로 결정합니다.
    	mid = (low + high) // 2 
        # 3. data[mid] 와 target 이 서로 같으면 목적을 달성했으므로 탐색을 종료합니다.
        if target == data[mid]: 
        	return True 
        # 4. 만약 target < data[mid] 이면 high = mid-1 로 업데이트 한 후, 함수를 호출합니다.
        elif target < data[mid]: 
        	return binary_search(data, target, low, mid - 1) 
        else: 
        	# 5. 만약 target > data[mid] 라면 low = mid+1 로 업데이트 한 후, 함수를 호출합니다.
        	return binary_search(data, target, mid + 1, high)

요걸 변형해 주면 범위 탐색도 빠르게 가능하다는 거!

 

 

 

 

출처: https://codepractice.tistory.com/101 [코딩 연습]