Problem:


探索

 「探索」とは、たくさんの情報の中から望みの情報を得る操作のことです。身近な例では、合格発表の時の「たくさんの受験番号から自分の受験番号を見つける」ことや、電話帳から「会津太郎さんの電話番号を見つける」ときなどがあります。この探索という操作はコンピュータの分野でも広く用いられています。

探索の方法は沢山あります。探索の対象となるデータが、小さい順(または大きい順)に並べられている場合に使うことができる探索の方法を考えます。

小さい順(または大きい順)に並べられているデータ列の中央に位置する値と目的の値との大小関係を用いて、中央に位置する値から前半部分を探索範囲にするか後半部分を探索範囲にするかを決めることで、探索の範囲を絞っていく方法があります。手順は以下のようになります。

データの列の全体を探索の範囲とします。

探索の範囲の中央に位置する値を調べます。

目的の値と中央に位置する値が一致すれば探索を終了します。

目的の値と中央に位置する値よりも小さければ前半部分を探索の範囲とし、大きければ後半部分を探索の範囲として2.へ戻ります。

 以下は上述した探索の方法の例です。この例での目的の値は51です。それぞれのデータには番号
(index)が振られており、この番号は0から始まっています。

 

ステップ1: 最初は番号0~6全体を探索の範囲とします。

ステップ2: 探索の範囲の中央に位置する値を調べます。ただし、「中央に位置する値」とは、(左側の番号+右側の番号)を2で割った番号の位置にある値とします。つまり、この場合、(0 + 6) ÷ 2 を計算し、番号3にある値(36)が中央に位置する値となります。

ステップ3:目的の値(51)と中央に位置する値(36)を比較します。

ステップ4:ステップ3の結果から、目的の値は中央に位置する値より大きいので、後半部分にあたる番号4 (中央に位置する値の隣)以降を探索の範囲とします。同様の手順で探索の範囲の中央に位置する値を調べ、目的の値が中央に位置する値より小さければ前半部分を探索の範囲とし、大きければ後半部分を探索の範囲として、探索の範囲を小さくしていきます。(ステップ2~ステップ4の繰り返し)目的の値が中央に位置する値と一致するか、探索の範囲がつきてしまった時に探索を終了します。

 n 個の数値の配列を入力とし、目的の値と中央に位置する値を比較した回数を出力するプログラムを作成してください。ただし、中央に位置する値の番号を計算したとき、割り切れない場合は、小数点以下を切り捨てた値をその番号とすることとします。
与えられるデータ列は小さい順に整列されているものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下の形式で与えられます。

n
a1
a2
:
an
k

1 行目に数値の数 n (1 ≤ n ≤ 100) 、続く n 行に i 個目の数値 ai (1 ≤ ai ≤ 100000, 整数) が与えられます。

続く行に探索する値 k (1 ≤ k ≤ 100000) が与えられます。

Output

データセット毎に探索が終わるまでの比較回数を１行に出力します。

Sample Input

7
11
15
23
36
51
61
86
51
4
1
2
3
5
4
0

Output for the Sample Input

3
3



Sample input:
7
11
15
23
36
51
61
86
51
4
1
2
3
5
4
0


Sample output:
3
3

Submission status: Wrong Answer

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median = int(math.floor(float(n)/2))
    if len(L) == 0 or L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Wrong Answer

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median = int(math.floor(float(n)/2))
    if len(L) == 1 or L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Wrong Answer

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median1 = int(math.floor(float(n-1)/2))
    median2 = int(math.floor(float(n)/2))
    if len(L) == 1 or L[median1] == check or L[median2] == check:
        return count
    elif L[median2] < check:
        L = L[median2+1:]
    elif check < L[median1]:
        L = L[:median1]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Wrong Answer

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median1 = int(math.floor(float(n-1)/2))
    median2 = int(math.floor(float(n)/2))
    if len(L) == 1 or len(L) == 2:
        return count
    elif L[median1] == check or L[median2] == check:
        return count
    elif L[median2] < check:
        L = L[median2+1:]
    elif check < L[median1]:
        L = L[:median1]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Wrong Answer

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median = int(math.floor(float(n)/2))
    if len(L) == 1:
        return count
    elif L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Wrong Answer

Solution code:
def f(check, n, L, count):
    count += 1
    median = n/2
    if len(L) == 1 or L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Wrong Answer

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

"""
import sys
from sys import stdin
input = stdin.readline


def b_search(data, k):
    count = 0
    l = 0
    r = len(data) - 1

    while True:
        count += 1
        mid = (l + r) // 2
        if (data[mid] == k) or (l == r):
            break
        if data[mid] > k:
            r = mid
        else:
            l = mid + 1
    return count



def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [int(input()) for _ in range(n)]
        k = int(input())
        result = b_search(data, k)
        print(result)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
def bisect(L,a):
    n = len(L)
    if n < 1 or L[n/2] == a:
        return 1
    if L[n/2] > a:
        return bisect(L[:n/2],a) + 1
    return bisect(L[n/2+1:],a) + 1

while True:
    n = input()
    if n == 0:
        break
    print bisect([input() for _ in xrange(n)],input())

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	N = [int(raw_input()) for i in range(n)]
	s = input()
	i = n/2
	c = 1
	while i > 0:
		c += 1
		if N[i] == s:
			break
		elif N[i] < s:
			i /= 2
		else:
			if i != n-1:
				i = min(n-1,i+i/2)
			else:
				break
	print c

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	N = [int(raw_input()) for i in range(n)]
	s = input()
	i = n/2
	c = 1
	while n/2**c > 0:
		c += 1
		if N[i] == s:
			break
		elif N[i] < s:
			i /= 2
		else:
			i += n/2**c
	print c

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	N = [int(raw_input()) for i in range(n)]
	s = input()
	i = n/2
	c = 1
	while n/2**c > 0:
		c += 1
		if N[i] == s:
			break
		elif N[i] < s:
			i -= n/2**c
		else:
			i += n/2**c
	print c

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	N = [int(raw_input()) for i in range(n)]
	s = input()
	i = n/2
	c = 1
	while i > 0:
		c += 1
		if N[i] == s:
			break
		elif N[i] < s:
			i /= 2
		else:
			i = min(n-1,i+i/2)
	print c

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve(a, s):
	left = 0
	right = len(a) - 1
	
	cnt = 0
	while left <= right:
		mid = (left + right) / 2
		cnt += 1
		if a[mid] == s:
			break
		elif a[mid] < s:
			left = mid + 1
		else:
			right = mid - 1
	return cnt


while True:
	n = int(raw_input())
	if n == 0: break
	a = [ int(raw_input()) for _ in xrange(n) ]
	s = int(raw_input())
	print solve(a, s)

Submission status: Accepted

Solution code:
while 1:
    l,r=0,int(input())
    if r==0:break
    a=[int(input()) for _ in range(r)]
    r-=1;c=0
    k=int(input())
    while l<=r:
        c+=1
        m=(l+r)//2
        if a[m]==k:break
        if a[m]<k:l=m+1
        else:r=m-1
    print(c)

Submission status: Accepted

Solution code:
def nibutan(f_id,e_id,f_num,count):
    
    
    m_id = int((f_id + e_id) / 2)
    m_num = n_lis[m_id]

   
    if (f_id > e_id):
        return count
    else:
        count += 1

        if m_num > f_num:
            return(nibutan(f_id,m_id -1,f_num,count))
        elif m_num < f_num:
            return(nibutan(m_id + 1,e_id,f_num,count))
        else:
            return count
                
while True:
    global n_lis

    n = int(input())
    if n == 0:
        break
    n_lis = []
    for i in range(n):
        n_lis.append(int(input()))
    f_n = int(input())
    ans = nibutan(0,n - 1,f_n,0)
    print(ans)

Submission status: Accepted

Solution code:
# Aizu Problem 0188: Search
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def search(n, A, s):
    cnt = 0
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        cnt += 1
        if A[mid] == s:
            return cnt
        elif A[mid] > s:
            right = mid - 1
        else:
            left = mid + 1
    return cnt

while True:
    n = int(input())
    if n == 0:
        break
    A = [int(input()) for _ in range(n)]
    s = int(input())
    print(search(n, A, s))

Submission status: Accepted

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

"""
import sys
from sys import stdin
input = stdin.readline


def b_search(data, k):
    count = 0
    l = 0
    r = len(data) - 1

    while r >= l:
        count += 1
        mid = (l + r) // 2
        if data[mid] == k:
            break
        if data[mid] > k:
            r = mid - 1
        else:
            l = mid + 1
    return count



def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [int(input()) for _ in range(n)]
        k = int(input())
        result = b_search(data, k)
        print(result)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def search(n,d,t):
    b = 0
    e = n-1
    r = 0
    while True:
        if b > e:
            return r
        else:
            r += 1
            i = (b+e)//2
            if t == d[i]:
                return r
            elif t < d[i]:
                e = i - 1
            else:
                b = i + 1
while True:
    n = int(input())
    if n == 0:
        break
    d = [int(input()) for i in range(n)]
    t = int(input())

    m = search(n,d,t)
    print(m)

Submission status: Accepted

Solution code:
def binary_search(num_list, num):
    left = 0
    right = len(num_list) - 1

    count = 0

    while left <= right:
        mid = left + (right - left) // 2
        count += 1

        if num_list[mid] == num:
            break
        elif num_list[mid] < num:
            left = mid + 1
        else:
            right = mid - 1

    return count


while True:

    input_count = int(input())

    if input_count == 0:
        break

    num_list = [int(input()) for _ in range(input_count)]

    search_number = int(input())

    result = binary_search(num_list, search_number)

    print(result)

Submission status: Accepted

Solution code:
# AOJ 0177 Distance Between Two Cities
# Python3 2018.6.20 bal4u

while True:
	n = int(input())
	if n == 0: break
	a = [0]*120
	for i in range(n): a[i] = int(input())
	k = int(input())
	cnt = 0
	l, r = 0, n-1
	while l <= r:
		cnt += 1
		m = (l + r) >> 1
		if k == a[m]: break
		if k < a[m]: r = m-1
		else: l = m+1
	print(cnt)

Submission status: Accepted

Solution code:
def search_num(k, alst):
  left = 0
  right = len(alst) - 1
  cnt = 0
  while left <= right:
    mid = (left + right) // 2
    cnt += 1
    if alst[mid] == k:
      return cnt
    if alst[mid] < k:
      left = mid + 1
    else:
      right = mid - 1
  return cnt

while True:
  n = int(input())
  if n == 0:
    break
  alst = [int(input()) for _ in range(n)]
  k = int(input())
  print(search_num(k, alst))

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:break
    L=[input() for i in range(n)]
    v=input()
    l,r=0,len(L)-1
    cnt=0
    while l<=r:
        m=(l+r)/2
        if L[m]==v:
            print cnt+1
            break
        elif L[m]<v:
            l=m+1
        elif L[m]>v:
            r=m-1
        cnt+=1
    else:
        print cnt

Submission status: Accepted

Solution code:
def bisect(L,a):
    if L == []:
        return 0
    n = len(L) - 1
    if L[n/2] == a:
        return 1
    elif L[n/2] > a:
        return bisect(L[:n/2], a) + 1
    return bisect(L[n/2+1:], a) + 1

while True:
    n = input()
    if n == 0:
        break
    print bisect([input() for _ in xrange(n)], input())

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	N = [input() for i in range(n)]
	s = input()
	l,r= 0,n-1
	c = 0
	while l <= r:
		i = (l + r)/2
		c += 1
		if N[i] == s:
			break
		elif N[i] < s:
			l = i + 1
		else:
			r = i - 1
	print c

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(input())
    if N == 0:
        return False
    A = [int(readline()) for i in range(N)]
    k = int(readline())

    ans = 0
    left = 0; right = N-1
    while left <= right:
        mid = (left + right) >> 1
        v = A[mid]
        ans += 1
        if v == k:
            break
        if v < k:
            left = mid+1
        else:
            right = mid-1
    write("%d\n" % ans)
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
def search(data, key):
    cnt = 0
    left, right = -1, len(data)

    while right - left > 1:
        mid = (left + right) // 2
        cnt += 1
        if data[mid] == key: break
        elif data[mid] > key:
            right = mid
        else:
            left = mid

    return cnt

def solve():
    N = int(input())
    if N == 0: return -1
    data = [int(input()) for i in range(N)]
    k = int(input())
    return search(data, k)

while True:
    ans = solve()
    if ans == -1: break
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break

    array = []
    for _ in range(n):
        a = int(input())
        array.append(a)
    k = int(input())

    n -= 1
    l = 0
    cnt = 0
    while l <= n:
        cnt += 1
        m = (l+n) // 2
        if array[m] == k:
            break

        if array[m] < k:
            l = m + 1
        else:
            n = m - 1
    print(cnt)

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0: break
    a = [int(input()) for _ in range(n)]
    k = int(input())
    l, r, c = 0, n-1, 0
    while l <= r:
        c += 1
        m = (l+r) >> 1
        if k == a[m]:
            break
        elif k < a[m]:
            r = m-1
        else:
            l = m+1
    print(c)

Submission status: Runtime Error

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median = int(math.floor(float(n)/2))
    if len(L) == 1 or L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n-1, L, 0)

Submission status: Runtime Error

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median = int(math.floor(float(n)/2))
    if len(L) == 1 or L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)-1
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n-1, L, 0)

Submission status: Runtime Error

Solution code:
import math

def f(check, n, L, count):
    count += 1
    median = int(math.floor(float(n-1)/2))
    if len(L) == 1:
        return count
    elif L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Runtime Error

Solution code:
def f(check, n, L, count):
    count += 1
    median = (n-1)/2
    if len(L) == 1 or L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

Submission status: Runtime Error

Solution code:
while 1:
    l,r=0,int(input())
    a=[int(input()) for _ in range(r)]
    r-=1;c=0
    k=int(input())
    while l<=r:
        c+=1
        m=(l+r)//2
        if a[m]==k:break
        if a[m]<k:l=m+1
        else:r=m-1
    print(c)

Submission status: Runtime Error

Solution code:
def nibutan(f_id,e_id,f_num,count):
    
    
    m_id = int((f_id + e_id) / 2)
    m_num = n_lis[m_id]

    count += 1
    if (f_id > e_id):
        return count
    else:

        if m_num > f_num:
            return(nibutan(f_id,m_id -1,f_num,count))
        elif m_num < f_num:
            return(nibutan(m_id + 1,e_id,f_num,count))
        else:
            return count
                
while True:
    global n_lis

    n = int(input())
    if n == 0:
        break
    n_lis = []
    for i in range(n):
        n_lis.append(int(input()))
    f_n = int(input())
    ans = nibutan(0,n,f_n,0)
    print(ans)

Submission status: Runtime Error

Solution code:
def search(n,d,t):
    b = 0
    e = n
    r = 0
    while True:
        r += 1
        if b > e:
            return r
        else:
            i = (b+e)//2
            if t == d[i]:
                return r
            elif t < d[i]:
                e = i - 1
            else:
                b = i + 1
while True:
    n = int(input())
    if n == 0:
        break
    d = [int(input()) for i in range(n)]
    t = int(input())

    m = search(n,d,t)
    print(m)

Submission status: Runtime Error

Solution code:
def search(n,d,t):
    b = 0
    e = n
    r = 0
    while True:
        r += 1
        if b > e:
            return r
        else:
            i = (b+e)//2
            if t == d[i]:
                return r
            elif t < d[i]:
                e = i - 1
            else:
                b = i + 1
while True:
    n = int(input())
    if n == 0:
        break
    d = [int(input()) for i in range(n)]
    t = int(input())

    m = search(n,d,t)
    print(m)

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	N = [int(raw_input()) for i in range(n)]
	s = input()
	i = n/2
	c = 1
	while i > 0:
		c += 1
		if N[i] == s:
			break
		elif N[i] < s:
			i /= 2
		else:
			i += i/2
	print c