[이분 탐색(결정 알고리즘) & 그리디 알고리즘] 파이썬 알고리즘 문제 3-1 "이분 검색"

이분 탐색('Binary Search')

 

[시간복잡도]

O(logN) : 이진탐색은 계속해서 리스트를 반으로 줄이는 것이기 때문에 logN에 해당한다.

 

[공간복잡도]

O(N) 

 

---

 

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

 

 

💯 Solution ①

 

import sys
sys.stdin=open("input.txt","rt")
 
# n : 리스트의 갯수  , m : 찾아야하는 수
n, m = map(int,input().split())
a = list(map(int,input().split()))
# 오름차순으로 정렬
a.sort()
# lt : 제일 왼쪽 인덱스 번호 , rt : 제일 오른쪽 인덱스 번호
lt=0
rt=n-1
 
for i in range(n):
    # mid : 가운데 인덱스 번호
    mid = (lt + rt)//2
    # 중간값이 m과 같을 때
    if a[mid]==m:
        # 인덱스에 +1를 해야 몇번째인지 계산할 수 있다.
        print(mid+1)
        # for문 중단
        break
    # 중간값이 m보다 클 때
    elif a[mid] > m:
        rt=mid-1
    # 중간값이 m보다 작을 때
    else:
        lt=mid+1

 

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

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

 

 

 

💯 Solution ②

: Tutor's Code

 

import sys
sys.stdin=open("input.txt","rt")
 
# n : 리스트의 갯수  , m : 찾아야하는 수
n, m = map(int,input().split())
a = list(map(int,input().split()))
# 오름차순으로 정렬
a.sort()
# lt : 제일 왼쪽 인덱스 번호 , rt : 제일 오른쪽 인덱스 번호
lt=0
rt=n-1
 
for i in range(n):
    # mid : 가운데 인덱스 번호
    mid = (lt + rt)//2
    # 중간값이 m과 같을 때
    if a[mid]==m:
        # 인덱스에 +1를 해야 몇번째인지 계산할 수 있다.
        print(mid+1)
        # for문 중단
        break
    # 중간값이 m보다 클 때
    elif a[mid] > m:
        rt=mid-1
    # 중간값이 m보다 작을 때
    else:
        lt=mid+1

튜터님과의 코드가 굉장히 유사하지만,

반복문을 시작하는 조건을 다르게 정의했다.

 

나는 for 문을 사용해서 for i in range(n): 을 사용했고

튜터님은 while lt<=rt: 로 lt값이 rt값과 같거나 rt값이 더 크다면 반복문을 실행하는 것으로 작성을 했다.

 

 

📚 참고

(이진 탐색 정리)

 

infinitt.tistory.com/286

 

알고리즘 ) 이진 탐색, 이분 탐색 (Binary serach) _ python 재귀

 

⚙️저장소

 

github.com/JiHoon-JK/Algorithm/blob/main/inflearn/python/%EC%84%B9%EC%85%984-1.py

JiHoon-JK/Algorithm