[이코테] 이분탐색 - 고정점 찾기 with 파이썬

1. 문제

• 고정점 : 수열의 원소 중 그 값이 인덱스와 동일한 원소

• 고정점을 찾는 프로그램을 만들라.

입력 조건

• n은 1 ~ 1000000
• 각 원소값은 -1e9 ~ 1e9

2. 아이디어

• 이진탐색은 최적화 대상, 목적함수를 구하는 것이 중요

• 최적화 대상은 인덱스

  • 인덱스의 최소는 0, 최대는 n-1
  • 인덱스에 해당하는 값이 인덱스보다 크면, 인덱스 보다 작은 쪽을 탐색한다.
  • 인덱스에 해당하는 값이 인덱스보다 작으면, 인덱스 보다 큰 쪽을 탐색한다.

• 재귀함수로 binary search를 구현

3-1. 예제코드 (재귀 version)

# 이진탐색 함수 
def binary_search(array, start, end):
    if start > end :   # 탐색 완료했는데 답이 없는 경우 
        return None 
    mid = (start+end)//2        
    # 고정점을 찾으면 
    if array[mid] == mid :  
        return mid
    # 인덱스에 해당하는 값이 인덱스보다 크면, 인덱스 보다 작은 값 탐색
    elif array[mid] > mid:
        return binary_search(array, start, mid -1 )
    # 인덱스에 해당하는 값이 인덱스보다 작으면, 인덱스보다 큰 값 탐색
    else :
        return binary_search(array, mid+1, end)

# 입력
n = int(input())
array = list(map(int, input().split()))

# 함수 실행, 최소값은 0 , 최대값은 n-1
index = binary_search(array, 0, n-1)

if index == None:
    print(-1)
else :
    print(index)

3-2. 예제코드2 (반복문 version)

n = int(input())

nums = list(map(int, input().split()))

start = 0
end = len(nums) - 1

while start <= end:
    mid = (start+end)//2
    
    if nums[mid] == mid :
        print(mid)
        break
    elif nums[mid] < mid :
        start = mid+1
    else :
        end = mid - 1

4. 배운점

• 이진탐색 기본 함수 재귀버전 구현 리마인드

참조

• 이것이 취업을 위한 코딩테스트다. with 파이썬