이분검색

이분검색이란?
: 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

내가 생각한 코드

#1. Alt+W+N 입력하고 Alt+W+V :

import sys
sys.stdin = open("input.txt", "rt")

n, m = map(int,input().split())
board = list(map(int,input().split()))
board.sort()
p = 0
q = n

while(True):
    if board[(p+q)//2] > m:
        q = (p+q)//2
    if board[(p+q)//2] < m:
        p = (p+q)//2
    else:
        num = (p+q)//2
        break
print(num+1)

아마 줄어진 경우가 a, b 일때 즉 길이가 2일때..
예를 들어 11 12 일때 구하고자 하는 값이 12라면,
두가지 중에는 항상 p+q//2 로 정하게 되므로 break 될 일이 없다...

강의를 들어보자...

선생님 코드

맨 왼쪽을 가르키는 변수 lt와 오른쪽 가르키는 rt 가 필요하다
중간을 가르키는 lt가 필요하다.
mid(lt+rt)//2
a[mid] == m
rt = mid-1 이나 lt = mid+1 로 좁혀 나간다.
+1씩 하므로 길이가 2일 경우에도 한칸씩 늘려 나가면서 확인 가능하다.!!!!!!!!

#1. Alt+W+N 입력하고 Alt+W+V :

import sys
sys.stdin = open("input.txt", "rt")

#맨 왼쪽을 가르키는 변수 lt와 오른쪽 가르키는 rt 가 필요하다
# 중간을 가르키는 lt가 필요하다.
# mid(lt+rt)//2
# a[mid] == m 
# rt = mid-1 이나 lt = mid+1 로 좁혀 나간다.
# +1씩 하므로 길이가 2일 경우에도 한칸씩 늘려 나가면서 확인 가능하다.

n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
lt = 0
rt = n-1

while lt<=rt:
   mid = (lt + rt)//2
   if a[mid] == m:
       print(mid+1)
       break
   elif a[mid]>m:
       rt = mid -1
   else:
       lt = mid +1