이분탐색(결정알고리즘) & 그리디 알고리즘_1_이분 검색

 

Problem

임의의 N개의 숫자가 입력으로 주어집니다.

N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요.

단 중복값은 존재하지 않습니다.

 

▣ 입력설명

 

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

▣ 출력설명

 

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

 

▣ 입력예제

 

8 32

23 87 65 12 57 32 99 81

 

▣ 출력예제

 

3

 

'이분 검색(Binary Search)' 를 하기 위해서는?

1. 이분 검색을 위해서는 무조건 오름차순/내림차순으로 리스트를 정렬해야한다.
2. 처음에 lt(제일 왼쪽 인덱스 값), rt(제일 오른쪽 인덱스 값)를 설정한다.
3. 해당 리스트의 인덱스에서 가운데 값을 mid로 설정한다. mid=((lt+rt)//2)
4. 반복문을 통해서 리스트의 [mid] 값이 같은지 파악한다.
5. 다르다면, 경우에 따라서 lt와 rt의 값을 변경하면서 범위를 좁힌다.
6. 리스트의 [mid]값이 찾으려는 값과 같다면 반복문을 종료한다.

import sys
sys.stdin = open('input.txt', 'r')
n, answer = map(int, input().split())
arr = list(map(int, input().split()))

leftP = 0;                          #왼쪽 값
rightP = n-1                        #오른쪽 값

arr.sort()                          # 오름차순 정렬

while leftP <= rightP :             #leftP가 rightP보다 작을때 : 참
    midP = (leftP + rightP) // 2    #중간 값(반복할때마다 갱신)

    if arr[midP] == answer:         #중간 값과 찾고자 하는 값이 동일할 경우
        print(midP+1)               #인덱스 출력
        break
    elif arr[midP] > answer:        #찾는 값이 mid 보다 작은 경우(정답은 mid 왼쪽에 있다)
        rightP = midP - 1           #mid 오른쪽을 버린다(mid 가 맨 오른쪽이 된다)
    else :
        leftP = midP + 1            #찾는 값이 mid 보다 큰 경우(정답은 mid 오른쪽에 있다)

 

참고 - 재귀

def binarySearch(arr, start, end, target):
    global cnt
    mid = (start + end)//2
    mid_value = arr[mid]
    cnt += 1
    if target == mid_value:
        print("%d차 시도 , 탐색 완료 !! 인덱스 번호:%d"%(cnt, mid+1))
        
    elif mid > target:
        end = mid-1
        print("%d차 시도 :"%cnt,start,end)
        binarySearch(arr, start, end, target)
        
    elif mid < target:
        start = mid +1
        print("%d차 시도  :"%cnt, start, end)
        binarySearch(arr, start, end, target)
        
    else:
        return False



arr = [i for i in range(100)]
arr.sort()
target = 15
start = 0
end = len(arr) -1 
cnt = 0
binarySearch(arr, start, end, target)