Go: // binary search

package main

import (
	"bufio"
	"os"
	"strconv"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	for scanner.Scan() {
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		a := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			a[i], _ = strconv.Atoi(scanner.Text())
		}
		scanner.Scan()
		k, _ := strconv.Atoi(scanner.Text())
		cnt := 0
		low, high := 0, n-1
		for low <= high {
			cnt++
			mid := (low+high)>>1
			if k == a[mid] {
				break
			}
			if k < a[mid] {
				high = mid-1
			} else {
				low = mid+1
			}
		}
		fmt.Println(cnt)
	}
}

C++: #include <bits/stdc++.h>
using namespace std;

int main(void){
    int n;
    while(cin >> n, n){
        int data[10000];
        int need;
        for(int i=0; i < n; i++)
            cin >> data[i];
        cin >> need;

        int before = 0, after = n-1;
        int cnt = 0;
        while(1){
            int mid = (after + before) / 2;
            cnt++;
            if(need == data[mid])
                break;
            if(before >= after)
                break;
            if(data[mid] > need)
                after = mid-1;
            else
                before = mid+1;
        }
        cout << cnt << endl;
    }
    return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<bitset>
#include<functional>
#include<climits>
using namespace std;
typedef pair<int,int>pii;
const int INF=1e9;
const int dx[]={0,-1,0,1},dy[]={-1,0,1,0};



int main(){
    int n;
    while(cin>>n,n){
        int v[100];
        for(int i=0;i<n;i++)cin>>v[i];
        int t;cin>>t;
        int ub=n-1,lb=0;
        int cnt=0;
        bool flag=true;
        while(ub>=lb){
            cnt++;
            int mid=(ub+lb)/2;
            if(v[mid]>t)ub=mid-1;
            else if(v[mid]<t)lb=mid+1;
            else if(v[mid]==t){
                cout<<cnt<<endl;
                flag=false;
                break;
            }
        }
        if(flag)cout<<cnt<<endl;
    }
    return 0;
}

C++: #include <iostream>
#include <algorithm>
using namespace std;

int T[100010];
int find(int m,int x){
	int r=0,l=m-1,ans=0;
	while(1){
		ans++;
		if(T[(r+l)/2]==x)return ans;
		else if(r==l)break;
		if(T[(r+l)/2]>x)l=(r+l)/2-1;
		else if(T[(r+l)/2]<x)r=(r+l)/2+1;
	}
	return ans;
}
int main(){
	int n,k,num,ans;
	while(1){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>T[i];
		}
		cin>>k;
		ans=find(n,k);
		cout<<ans<<endl;
	}
	return 0;
}

C++: //43
#include<iostream>

using namespace std;

int main(){
  for(int n;cin>>n,n;){
    int a[100];
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    int ans=1;
    int f=0,l=n-1;
    int g;
    cin>>g;
    for(;;ans++){
      int m=f+(l-f)/2;
      if(a[m]==g||l-f<=0){
	break;
      }else if(a[m]>g){
	l=m-1;
      }else{
	f=m+1;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

C++: #include<stdio.h>

int main(void)
{
	int x[100];
	int st,fn,a,n,i,ty,kai;
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		kai=1;  st=0; fn=n-1;
		for(i=0;i<n;i++) scanf("%d",&x[i]);
		scanf("%d",&a);
		while(0==0){
			ty=(st+fn)/2;
			if(a==x[ty]||st==fn)break;
			else if(a>x[ty])  st=ty+1;
			else fn= ty-1;
			kai++;
		}
		printf("%d\n",kai);
	}
	return 0;
}

C++: import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int b = sc.nextInt();
			if(b == 0){
				//System.out.println("break");
				break;
			}
			int[] a = new int[b];
			int left,right,searchvalue;
			for(int i=0; i < a.length; i++){
				a[i] = sc.nextInt();
			}
			searchvalue = sc.nextInt();
			left = 0; right = a.length-1;
			System.out.println(solve(left, right, searchvalue, a));
		}
	}

	int solve(int left, int right,int sv,int[] a){
		int index = (left + right) / 2;
		int cnt;
		//System.out.println("left:"+left+" right:"+right+" sv:"+sv+" a[index]:"+a[index]);
		if(a[index] == sv){
			return 1;
		}else if(left == right){
			return 1;
		}else if(a[index] < sv){
			left = index;
			return 1 + solve(++left, right, sv, a);
		}else if(a[index] > sv){
			right = index;
			return 1 + solve(left, --right, sv, a);			
		}
		return 0;
		
		/*
		if(cnt == a.length-1){
			System.out.println(cnt);
			return;
		}
		if(a[(left + right) / 2] < sv){
			System.out.println("left:"+left+" right:"+right);
			if(left <= right){
				left = (left + right) / 2 + 1;
				solve(left, right,sv, a, ++cnt);
			}else{
				System.out.println(++cnt);
			}
		}else if(a[(left + right) / 2] > sv){
			System.out.println("left:"+left+" right:"+right);
			if(left < right){
				right = (left + right) / 2 - 1;
				solve(left, right,sv, a, ++cnt);
			}else{
				System.out.println(++cnt);
			}
		}else{
			System.out.println(++cnt);
		}
		*/
	}
}

C++: #include <bits/stdc++.h>

using namespace std;

#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ELEM(array) (sizeof (array)/sizeof *(array))
#define MAX_N 100
typedef long long ll;

int n = -1;
int a[101];
int k;

void serch(int k)
{
	
	int ans = 1;

	int lb = 0; int ub = n-1;
	while (ub - lb>1)
	{
		int mid = (lb + ub) / 2;
		if (a[mid] == k) {
			ans++; break;
		}
		else if (a[mid] > k){
			ub = mid;
			ans++;
		}
		else {
			lb = mid;
			ans++;
		}
	}
	cout <<ans << endl;
	
	return;
}
int main()
{
	while (cin>>n&& n!=0)
	{
		
		REP(i, n){
			cin >> a[i];
		}
		
		cin >> k;
		serch(k);
	}


	return 0;
}

C++: #include<iostream>

using namespace std;



int main(){
	int num[101],r,l,c;
	int kazu, target, t;
	int i;

	while (1){
		t = 0;
		cin >> kazu;

		if (kazu == 0){
			break;
		}

		for (i = 0; i < kazu; i++){
			cin >> num[i];
		}

		cin >> target;


		l = 0;
		r = (kazu - 1);
		t = 0;
		while (1){
			c = (l + r) / 2;
			t++;
			if (num[c] == target){
				break;
			}else if (r==l){
				break;
			}else if(num[c] < target){
				l = c + 1;
			}else{
				r = c - 1;
			}
								
		}


		cout << t << endl;
	}

}

C++: #include <stdio.h>
int a, b, c;
int main() {
	while(true) {
		scanf("%d", &a);
		if(a == 0) break;
		for(int i = 0; i < n; i++) scanf("%d", &b);
		c = 0;
		while (a != 0) {
			a /= 2; c++;
		}
		printf("%d\n", c);
	}
	return 0;
}

C++: #include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int main(){
	int set[101],n,k,cnt,a,b;
	while(1){
	cin >> n;
	if(n==0)break;
	for(int i=0;i<n;i++){
		cin >> set[i];
	}

	cin >> k;
	cnt=0;
	n--;
	a=n/2;
	for(int i=0,j=n;i<=j&&set[a]!=k;cnt++){
		a=(i+j)/2;
		if(set[a]<k) i=a+1;
		else j=a-1; 
	}
	cout << cnt　<< endl;
}
}