Problem:

Binary Search

 

  For a given sequence $A = \{a_0, a_1, ..., a_{n-1}\}$ which is sorted by ascending order, find a specific value $k$ given as a query.

Input

  The input is given in the following format.

$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$q$
$k_1$
$k_2$
:
$k_q$

The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $k_i$ are given as queries.

Output

  For each query, print 1 if any element in $A$ is equivalent to $k$, and 0 otherwise.

Constraints

  
$1 \leq n \leq 100,000$

  
$1 \leq q \leq 200,000$

  
$0 \leq a_0 \leq a_1 \leq ... \leq a_{n-1} \leq 1,000,000,000$
  
$0 \leq k_i \leq 1,000,000,000$

Sample Input 1

4
1 2 2 4
3
2
3
5

Sample Output 1

1
0
0



Sample input:
4
1 2 2 4
3
2
3
5


Sample output:
1
0
0

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))

def binary_search(val):
    left, right = 0, n-1
    while right - left > 1:
        mid = (right+left)//2
        if a[mid] == val: return 1
        if a[mid] < val:
            left = mid
        elif val < a[mid]:
            right = mid
    return 0

q = int(input())
for i in range(q):
    k = int(input())
    print(binary_search(k))

Submission status: Wrong Answer

Solution code:
a = int(input())

b = list(map(int,input().split()))

def nibu(low,high,i):
	middle = (low+high)//2
	if b[middle] <= i:
		low = middle
	else:
		high = middle

	if low == high:
		if i == b[low]:
			return 1 
		else:
			return 0

for i in range(a):
	k = int(input())
	print(nibu(0,len(b),k))

Submission status: Wrong Answer

Solution code:
input()

b = list(map(int,input().split()))

def nibu(low,high,i):
	middle = (low+high)//2
	if b[middle] <= i:
		low = middle
	else:
		high = middle

	if low == high:
		if i == b[low]:
			return 1 
		else:
			return 0
a = int(input())
for i in range(a):
	k = int(input())
	print(nibu(0,len(b),k))

Submission status: Wrong Answer

Solution code:
input()

b = list(map(int,input().split()))

def nibu(low,high,i):
	middle = (low+high)//2
	if b[middle] <= i:
		low = middle
	else:
		high = middle

	if low == high:
		if i == b[low]:
			return 1 
		else:
			return 0
a = int(input())
for i in range(a):
	k = int(input())
	print(nibu(0,len(b)-1,k))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))

def binary_search(val):
    left, right = 0, n-1
    while right - left >= 1:
        mid = (right+left)//2
        if a[mid] == val: return 1
        if a[mid] < val:
            left = mid
        elif val < a[mid]:
            right = mid
    return 0

q = int(input())
for i in range(q):
    k = int(input())
    print(binary_search(k))

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
    k=int(input())
    t=0
    max=n-1
    min=0
    while max-min>1:
        nn=math.floor((max-min)/2)
        if a[nn]==k:
            t=1
            print("1")
            break
        elif a[nn]>k:
            min=nn
        else :
            max=nn
    if t==0:
        print("0")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))

def binary_search(val):
    left, right = 0, n-1
    while right - left >= 0:
        mid = int((right+left)/2)
        if a[mid] == val: return 1
        if a[mid] < val:
            left = mid+1
        elif val < a[mid]:
            right = mid-1
    return 0

q = int(input())
for i in range(q):
    k = int(input())
    print(binary_search(k))

Submission status: Accepted

Solution code:
input()

b = list(map(int,input().split()))

def nibu(low,high,i):
	middle = int((low+high)/2)
	if low == high:
		if i == b[low]:
			return 1 
		else:
			return 0

	if b[middle] < i:
		low = middle + 1
		return nibu(low,high,i)
	elif b[middle] >= i:
		high = middle
		return nibu(low,high,i)

a = int(input())
for i in range(a):
	k = int(input())
	print(nibu(0,len(b)-1,k))

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
    k=int(input())
    t=0
    max=n-1
    min=0
    while max-min>1:
        nn=math.floor((max+min)/2)
        if a[nn]==k:
            t=1
            print("1")
            break
        elif a[nn]<=k:
            min=nn
        elif a[nn]>=k:
            max=nn
    if t==0:
        if a[max]==k or a[min]==k:
            t=1
            print("1")
        else:
            print("0")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# ITP2_6_A: Binary Search

from bisect import bisect


def search(li, x):
    """Returns True if x exists in li else False.
    Assumes li is sorted in ascending order.

    >>> search([1, 2, 3], 2)
    True
    >>> search([1, 2, 3], 4)
    False
    >>> search([1, 2, 3], 3)
    True
    >>> search([1, 2, 3], 0)
    False
    >>> search([1, 2, 3], 1)
    True
    """
    i = bisect(li, x)
    return 0 < i <= len(li) and li[i-1] == x


def run():
    n = int(input())
    a = [int(x) for x in input().split()]
    assert(n == len(a))

    q = int(input())
    for _ in range(q):
        k = int(input())
        if search(a, k):
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# AOJ ITP2_6_A: Binary Search
# Python3 2018.6.24 bal4u

from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)  # > 1,000,000,000
q = int(input())
for i in range(q):
	k = int(input())
	p = bisect_left(a, k)
	print(1 if a[p] == k else 0)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
    a = int(input())
    left = 0
    right = n
    flag = 0
    mid = (right - left) // 2 
    while left < right:
        if A[mid] == a:
            flag = 1
            break
        if a > A[mid]:
            left = mid+1
        else:
            right = mid
        mid = (left + right) //2
    print(flag)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin

    n = int(f_i.readline())
    A = list(map(int, f_i.readline().split()))
    A.append(100000001)

    q = int(f_i.readline())

    from bisect import bisect_left
    ans = []
    for i in range(q):
        k = int(f_i.readline())
        if k == A[bisect_left(A, k)]:
            ans.append('1')
        else:
            ans.append('0')

    print('\n'.join(ans))


solve()

Submission status: Accepted

Solution code:
def binarySearch(n, a):
    ok = -1  # when minimize
    ng = len(a)  # when maximize
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if a[mid] == n:
            return 1
        elif a[mid] < n:
            ok = mid
        else:
            ng = mid
    return 0


def resolve():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    kk = [int(input()) for _ in range(q)]
    for k in kk:
        print(binarySearch(k, a))


resolve()

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = sorted(list(map(int,input().split())))
a.append(1e20)

for i in range(int(input())):
    k = int(input())
    place = bisect.bisect_left(a,k)
    print(1 if a[place] == k else 0)

Submission status: Accepted

Solution code:
n = int(input())
a = set(map(int, input().split()))
q = int(input())
while q:
    q -= 1
    k = int(input())
    print(+(k in a))

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
a = list(map(int,input().split()))
a.append(1000000001)
q = int(input())
for i in range(q):
    k = int(input())
    p = bisect_left(a,k)
    print(1 if a[p] == k else 0)

Submission status: Accepted

Solution code:
import bisect

def main():
    n = int(input())
    a = list(map(int,input().split()))
    m = int(input())
    for _ in range(m):
        b = int(input())
        index = bisect.bisect_left(a,b)
        if index<n and a[index]==b  :print (1)
        else                        :print (0)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = set(map(int, input().split()))
q = int(input())
for i in range(q):
    k = int(input())
    print(int(k in a))

Submission status: Accepted

Solution code:
import bisect

n = int(input())
A = list(map(int, input().split()))
q = int(input())

minA = A[0]
maxA = A[-1]

for i in range(q):
    query = int(input())

    if (query < minA) or (maxA < query):
        print(0)
    else:
        if A[bisect.bisect_left(A, query)] == query:
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
input()
a = set(map(int, input().split()))
[print(1 if int(input()) in a else 0) for _ in range(int(input()))]

Submission status: Accepted

Solution code:
import bisect
def main():
    n = int(input())
    li = [int(a) for a in input().split()]
    q = int(input())

    for _ in range(q):
        k = int(input())
        l = bisect.bisect_left(li, k)
        exist = 0

        if 0 <= l <= len(li) - 1:
            if li[l] == k:
                exist = 1

        if 0 <= l - 1 <= len(li) - 1:
            if li[l-1] == k:
                exist = 1

        if 0 <= l + 1 <= len(li) - 1:
            if li[l + 1] == k:
                exist = 1

        print(exist)
main()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


N = int(input())
table = list(map(int,input().split()))

num_query = int(input())
for _ in range(num_query):
    tmp = int(input())
    L = 0
    R = len(table)-1
    mid = (L+R)//2
    loc = BIG_NUM
    while L <= R:
        if table[mid] == tmp:
            loc = mid
            break
        elif table[mid] > tmp:
            R = mid-1
        else:
            L = mid+1
        mid = (L+R)//2

    if loc == BIG_NUM:
        print("0")
    else:
        print("1")

Submission status: Accepted

Solution code:
import sys
n = int(input())
# a = tuple(input().split())
a = tuple(map(int,sys.stdin.readline().split()))
q = int(input())
# for _ in range(q):
#     if input() in a:print('1')
#     else:print('0')
for k in sys.stdin:
    k = int(k.strip())
    if k < a[0] or a[-1] < k:
        print('0')
    else:
        j1 = 0
        j2 = len(a)
        for _ in range(len(a)):
            j = (j1 + j2) // 2
            if k == a[j]:
                print('1')
                break
            else:
                if a[j] < k:j1 = j
                else:j2 = j
                if j1 + 1 == j2:
                    if k == a[j1] or k == a[j2]:
                        print('1')
                        break
                    else:
                        print('0')
                        break
            if _ == len(a)-1:print('0')

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    n = int(f_i.readline())
    A = list(map(int, f_i.readline().split()))
    A.append(1000000001)
    
    q = int(f_i.readline())
    
    from bisect import bisect_left
    ans = []
    for i in range(q):
        k = int(f_i.readline())
        if k == A[bisect_left(A, k)]:
            ans.append('1')
        else:
            ans.append('0')
    
    print('\n'.join(ans))

solve()

Submission status: Accepted

Solution code:
from bisect import *
input()
L = [int(x) for x in input().split()]
n = int(input())
for _ in range(n):
    x = int(input())
    i = bisect_left(L,x)
    if i >= len(L):
        print(0)
        continue
    if L[i] == x:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
from bisect import bisect


if __name__ == "__main__":
    n = int(input())
    nums = list(map(lambda x: int(x), input().split()))
    num_query = int(input())

    for _ in range(num_query):
        k = int(input())
        if nums[bisect(nums, k) - 1] == k:
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split( )))
a.sort()
q = int(input())
for _ in range(q):
    k = int(input())
    i = bisect.bisect_left(a,k)
    if  (i == n) or (i == 0 and a[0] > k):
        print(0)
    elif a[i] > k and k > a[i-1]:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)  # > 1,000,000,000
q = int(input())
for i in range(q):
	k = int(input())
	p = bisect_left(a, k)
	print(1 if a[p] == k else 0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Binary Search - Binary Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_6_A&lang=jp

"""
_ = input()
A = set(input().split())
for _ in range(int(input())):
    print(int(input() in A))

Submission status: Accepted

Solution code:
#binary search

def binary_search(A,x):

	target = x

	def bin_rec(left=0, right=len(A) - 1):

		if left > right:
			print("0")
			return

		else:
			mid = (left + right) // 2

			if A[mid] == target:
				print("1")
				return
			elif A[mid] < target:
				return bin_rec(mid + 1, right)
			else:
				return bin_rec(left, mid - 1)

	bin_rec()

if __name__ == '__main__':

	input()
	A = list(map(int,input().split()))
	n = int(input())

	for _ in range(n):
		x = int(input())
		binary_search(A,x)

Submission status: Accepted

Solution code:
def binary_search(list_sorted, x):
    low = 0
    high = len(list_sorted) - 1
    
    while low <= high:
        center = (low + high) // 2

        if   list_sorted[center] == x:
            return 1        
        elif list_sorted[center] <  x:
            low  = center + 1
        elif list_sorted[center] >  x:
            high = center - 1
        else:
            raise

    return 0


n = int(input())

A = tuple(map(int, input().split()))

q = int(input())


for _ in range(q):

    k = int(input())

    print(binary_search(A, k))

Submission status: Accepted

Solution code:
n = int(input())
box = list(map(int, input().split()))
def serch(s, l=0,r=n):
    while l < r:
        mid = (l+r)//2
        if box[mid] == s:
            return 1
        if s > box[mid]:l = mid+1
        if s < box[mid]:r = mid
    return 0
q = int(input())
for _ in range(q):
    print(serch(int(input())))

Submission status: Accepted

Solution code:
import bisect

n=int(input())
A=list(map(int,input().split()))
q=int(input())

for i in range(q):
    k=int(input())
    j=bisect.bisect(A,k)
    if j-1>=0 and A[j-1]==k:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
q = int(input())


def binary_search(A, k):
    left = 0
    right = len(A)
    while (left < right):
        mid = (left + right) // 2
        if A[mid] == k:
            return mid
        elif A[mid] < k:
            left = mid + 1
        else:
            right = mid
    return -1


for i in range(q):
    k = int(input())
    if binary_search(A, k) >= 0:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_6_A&lang=jp
#  Binary Search : python3
#  2018.11.26 yonezawa

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    l = list(map(int,input().split()))

    for i in range(int(input())):
        max = n -1
        min = 0
        mid = max // 2
        d = int(input())
        while True:
            if (l[mid] > d ):
                max = mid
            elif (l[mid] == d ):
                print ("1")
                break
            else:
                min = mid
            mid =  (max + min ) // 2 
            if ( mid == max or mid == min ):
                if ( l[mid] == d or l[max] == d):
                    print ("1")
                    break
                #print ("debug:",min,mid,max,l[mid])
                print ("0")
                break

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
n = int(input())
arr = list(map(int, input().split())) + [sys.maxsize]
nq = int(input())
lines = sys.stdin.readlines()
ans = [None] * nq
for i in range(nq):
    q = int(lines[i])
    idx = bisect.bisect_left(arr, q)
    ans[i] = '1' if arr[idx] == q else '0'

print('\n'.join(ans))

Submission status: Accepted

Solution code:
def find(ary, k):
    lo = 0
    hi = len(ary)
    while lo < hi:
        mid = lo + ((hi - lo) // 2)
        if ary[mid] == k:
            return mid
        if ary[mid] < k:
            lo = mid + 1
        else:
            hi = mid


def main():
    input()
    ary = [int(x) for x in input().split(' ')]
    q = int(input())
    for i in range(q):
        k = int(input())
        if find(ary, k) is not None:
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n = int(input())
num = list(map(int, input().split()))

q = int(input())
for _ in range(q):
    k = int(input())

    low = 0
    high = len(num)
    t = (low + high) // 2

    if k > num[-1]:
        print(0)
        continue

    while low <= high:
        if k == num[t]:
            break
        elif k > num[t]:
            low = t + 1
        elif k < num[t]:
            high = t - 1
        t = (low + high) // 2

    if k == num[t]:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
def binary_search(input_array, key):
    low = 0
    high = len(input_array) - 1
    while low <= high:
        mid = (low+high)//2
        if input_array[mid] == key:
            return 1
        elif input_array[mid] < key:
            low = mid + 1
        else:
            high = mid -1
    return 0
    



n = int(input())

input_array = raw_input().split(" ")
input_array = map(int, input_array)

q = int(input())

for i in range(q):
    print binary_search(input_array,int(input()))

Submission status: Accepted

Solution code:
from bisect import bisect
readline = open(0).readline
N = int(readline())
*A, = map(int, readline().split())
Q = int(readline())
ans = []
for q in range(Q):
    k = int(readline())
    ans.append("%d\n" % (A[bisect(A, k)-1] == k))
open(1, 'w').writelines(ans)

Submission status: Accepted

Solution code:
input(); A = set(input().split())
for _ in [0]*int(input()): print(1 if input() in A else 0)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
  k = int(input())
  t = bisect_left(a, k)
  if t>=n or a[t]!=k:
    print(0)
  else:
    print(1)