[이분탐색 / python] 13423. Three Dots

https://www.acmicpc.net/problem/13423

13423번: Three Dots

 

문제 분석

우선 탐색을 해야 하는 문제이다. 이진 탐색에 대한 이야기해보면 필요 없는 범위에 대한 탐색을 막음으로서 탐색을 좀 더 빠르게 수행하는 방법이다. 보통 O(logN)을 갖는다.

"""(이진탐색) 첫 번째 풀이-시간초과"""
t = int(input())
for i in range(t):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    # print(li)
    ans = 0

    for i in range(len(li)-2):
        for j in range(i+2, len(li)):
            if li[i] != li[j]:
                mid = (li[i]+li[j])//2
                flag = (li[i]+li[j])%2
                # print(li[i],mid, li[j])
                if mid in li and not flag: ans += 1
    print(ans)

"""(이진탐색) 두 번째 풀이-성공"""
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(len(li)-2):
        for j in range(i+2, len(li)):
            left = i
            right = j
            target = (li[left]+li[right]) / 2
            while left <= right:
                mid_idx = (left + right) // 2
                if li[mid_idx] == target: ans += 1; break
                elif li[mid_idx] < target: left = mid_idx+1
                elif li[mid_idx] > target: right = mid_idx-1
    print(ans)