문제 : https://www.acmicpc.net/problem/10816

▶ 이분탐색으로 arr에 해당 숫자 있는지 구하고, 해당 숫자의 '개수' 구하는 문제 

▶ 이분탐색은 항상 arr이 정렬 되어있어야 한다.

▶ 시행착오 1

한번 찾은 값을 다시찾지 않기위해서, 10,000,001 과 같이 큰 숫자로 바꿔버리면, arr의 정렬된 형태가 깨져버린다. 

ex) [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10] 의 경우, '3'에 대한 이분탐색을 하면 두번째 위치한 3이 먼저 출력된다.

다음 3은 현재 index의 왼쪽에 있다.

ex) [-1, -1, -1, 3, 3] 의 경우 '3'에 대한 이분탐색을 하면 첫번째 위치한 3이 먼저 출력된다.

다음 3은 현재 index의 오른쪽에 있다.

▶ 시행착오 2

한번 찾은 값을 다시 찾지 않기 위해서, 따로 표시하는 방법은 어떨까.

그러나 이러한 과정을 거치면 시간초과

표시한다해도, 그다음 이분탐색으로 넘어갈때 같은 값이 왼쪽에 있는지 오른쪽에 있는지 모른다.

▶ 풀이방법 1 : 배열 count 함수 + 딕셔너리 사용   → 시간초과 (오답)

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

dic = {}
for c in card:
    dic[c] = lst.count(c)
print(' '.join(str(dic[c]) for c in card))

▶ 풀이방법 2: 이분 탐색 할때 해당 값 찾은후, 배열에서 count + 딕셔너리 사용 

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

def BinarySearch(lst, n, low, high):
    if low > high: # 이분탐색 조건 
        return -1

    mid = (low + high) // 2

    if n < lst[mid]:
        return BinarySearch(lst, n, low, mid-1)
    elif n > lst[mid]:
        return BinarySearch(lst, n, mid+1, high)
    else:
        return lst[low:high+1].count(n)

dic = {}
for n in lst:
    low = 0
    high = len(lst)-1
    if n not in dic:
        dic[n] = BinarySearch(lst, n, low, high)
        
#print(dic)

print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

            

▶ 풀이방법 3 : arr은 정렬되어있으므로, 이분 탐색으로 해당 값을 찾고, 양 옆에 같은 수 몇개 있는지 세기

+ 딕셔너리 사용

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

def BinarySearch(arr, val, low, high):
    if low > high:
        return 0

    mid = (low + high) // 2

    if val < arr[mid]:
        return BinarySearch(arr, val, low, mid-1)
    elif val > arr[mid]:
        return BinarySearch(arr, val, mid+1, high)
    else:
        i = 1
        j = 1
        c = 1
        while mid - i >= 0:
            if arr[mid] != arr[mid-i]:
                break
            else:
                c += 1
            i += 1
        while mid + j < len(arr):
            if arr[mid] != arr[mid+j]:
                break
            else:
                c += 1
            j += 1
        return c

dic = {}
for n in lst:
    if n not in dic:
        dic[n] = BinarySearch(lst, n, 0, len(lst)-1)
        
#print(dic)     
print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

→ 이분 탐색 함수에서 해당 값 찾고, while 문 안에서 같지 않은것 찾았을때 즉시 빠져나오는 break 해주지 않으면 시간초과 

▶ 풀이방법 4: 딕셔너리만 사용 

from collections import Counter

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))


dic = {}

for n in lst:
    if n in dic: # 딕셔너리에 있으면
        dic[n] += 1
    else: # 딕셔너리에 없으면
        dic[n] = 1

print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

▶ 풀이방법 5: collections 라이브러리의 Counter() 사용

from collections import Counter

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))


counter = Counter(lst)

print(' '.join(str(counter[c]) if c in counter else '0' for c in card))

출처 : (https://chancoding.tistory.com/45)

문제 : https://www.acmicpc.net/problem/1654

▶ 이분탐색 조건1 : while (low <= high): ...

▶ 이분탐색 조건2 : low와 high의 초기값을 문제의 조건에 맞게 잘 설정해주자.

▶ 코드

n, k = map(int, input().split()) # 문제의 조건: 항상 N<=K

lst = []
for _ in range(n):
    lst.append(int(input()))
    
low = 1 # 시작을 1로 해야됨 !! (0으로 해버리면 mid로 나누는 부분에서 Error될 수 있음)
high = max(lst)
ans = -1
    
while low<=high: # 이분탐색 조건 !!
    mid = (low + high) // 2
    #print(low, mid, high)

    sum_val = 0
    for a in lst:
        sum_val += a//mid
            
    if sum_val >= k: # k개 '이상' 이라면..(=문제의 조건)
        ans = mid  # mid값으로 ans를 업데이트 해나간다.
        low = mid+1
    else:
        high = mid-1

print(ans)

문제 : https://www.acmicpc.net/problem/10815

▶ 코드

# 숫자 배열에만 이분탐색 가능
def BinarySearch(arr, val, low, high):
    if low > high:
        return False

    mid = (low + high) // 2

    if val < arr[mid]:
        return BinarySearch(arr, val, low, mid-1)
    elif val > arr[mid]:
        return BinarySearch(arr, val, mid+1, high)
    else:
        return True

n = int(input())
lst = list(map(int, input().split()))
lst.sort() # 이분탐색 하기전에 반드시 arr 정렬 !
m = int(input())
card = list(map(int, input().split()))
ans = []
for number in card:
    if BinarySearch(lst, number, 0, len(lst)-1):
        ans.append(1)
    else:
        ans.append(0)
#print(ans)
for a in ans:
    print(a, end=' ')

문제 : https://www.acmicpc.net/problem/1620

▶ 코드(딕셔너리)

# 이진탐색으로 풀이 불가
# 딕셔너리로 풀이

n, m = map(int, input().split())

dic1 = {}
dic2 = {}
for i in range(n):
    name = input()
    dic1[i+1] = name # i=1번째 부터 시작~
    dic2[name] = i+1

for _ in range(m):
    word = input()

    if word.isdigit(): # 입력된 str이 숫자형태면
        word = int(word)
        print(dic1[word])
    else:
        print(dic2[word])

▶ 이진탐색으로 어떻게 풀이..?

문제 : https://www.acmicpc.net/problem/1920

▶ 코드

import sys

# arr배열의 원소가 숫자일때만 가능 
def BinarySearch(arr, val, low, high):
    if low > high:
        return False

    mid = (low + high) // 2
    
    if val < arr[mid]:
        return BinarySearch(arr, val, low, mid-1)
    elif val > arr[mid]:
        return BinarySearch(arr, val, mid+1, high)
    else:
        return True
    
if __name__ == "__main__":
        N = int(sys.stdin.readline())
        A = list(map(int, sys.stdin.readline().split()))
        M = int(sys.stdin.readline())
        B = list(map(int, sys.stdin.readline().split()))

        A = sorted(A) # 매개변수로 들어갈 배열이 미리 정렬 되어있어야됨 

        for b in B:
            if BinarySearch(A, b, 0, N-1): # 배열, 찾으려는 원소, start, end
                print(1)
            else:
                print(0)