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 <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;
const int INF = 1 << 30;

int main()
{
	int n;

	while(cin >> n, n)
	{
		vector<int> T;
		int res = 0, num, up = n-1, low = 0;
		for(int i = 0; i < n; i++)
		{
			int a; cin >> a;
			T.push_back(a);
		}
		cin >> num;

		while( low <= up )
		{
			int mid = (up + low) / 2;
			res++;
			if(T[mid] > num)
			{
				up = mid-1;
			}
			else if(T[mid] < num)
			{
				low = mid+1;
			}
			else
			{
				break;
			}
		}
		
		cout << res << endl;
	}
}

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

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n) REP(i,0,n)

int n, l[100], t;

void solve() {
  rep(i,n) cin>>l[i];
  cin>>t;
  
  int lb = 0, ub = n-1, res = 1;
  while (ub != lb) {
    //if (lb > ub) break;
    int mid = (ub+lb)/2;
    //printf("lb=%d ub=%d mid=%d\n", lb, ub, mid);
    
    
    if (l[mid] < t) lb = mid + 1;
    else  if (l[mid] > t) {
      if (mid != 0) ub = mid - 1;
      else ub = mid;
    } else {
      break;
    }
    res++;
  }

  cout<<res<<endl;
}

int main (int argc, char const* argv[]) {
  while (cin>>n, n) {
    solve();
  }
  return 0;
}

C++: #include <iostream>
#include <vector>
using namespace std;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
typedef vector<int> VI;
#define pb                  push_back

int solve(VI vi, int t){
    int l = 0, r = vi.size()-1, cnt = 0;
    while(l<=r){
        int c = (l+r)/2;
        cnt++;
        if(vi[c] < t){ l = c+1; continue; }
        if(vi[c] > t){ r = c-1; continue; }
        break;
    }
    return cnt;
}

int main(void){
    int n, m;
    while(cin >> n && n){
        VI vi;
        REP(i,n){
            cin >> m;
            vi.pb(m);
        }
        cin >> m;
        cout << solve(vi, m) << endl;
    }
    return 0;
}

C++: #include<iostream>

int search(int *n, int key, int p, int l, int count){
	int c = (p+l)/2;
	if(n[c] == key || p==l)
		return count;
	else if(n[c] < key)
		return search(n, key, c+1, l, count+1);
	else
		return search(n, key, p, c-1, count+1);
}

int main(){
	int *data, n, key;
	while(true){
		std::cin >> n;
		if(n==0)
			return 0;
		data = new int[n];
		for(int i=0; i<n; i++)
			std::cin >> data[i];
		std::cin >> key;
		std::cout << search(data, key, 0, n-1, 1) << std::endl;
		delete[] data;
	}
}

C++: #include <iostream>
#include <math.h>
using namespace std;
int main(){
    int a, b, i1, times, max, min, tyuusinn;
    while(1){
    cin >> a;
    if(a==0){break;}
    i1=0;
    int w[a];
    while(1){
    cin >> b;
    w[i1]=b;
    i1++;
    if(i1==a){break;}
    }
    max=a-1;
    min=0;
    times=0;
    sort(w, w+a);
    cin >> b;
    while(1){
    times++;
        tyuusinn=(max+min)/2;
        if(max==min){break;}
    if(w[tyuusinn]==b){break;}
    else if(w[tyuusinn]<b){
        min=tyuusinn+1;
    }
    else{
        max=tyuusinn-1;
    }
    }
        cout << times << endl;
    }
    return 0;
}

C++: #include<stdio.h>

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

C++: #include <cstdio>

int n,k;
int a[200];

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		scanf("%d",&k);
		int l=0,r=n-1,cnt=0;
		while(1){
			cnt++;
			int m=(l+r)/2;
			//printf("%d %d %d %d %d %d\n",l,m,r,a[l],a[m],a[r]);
			if(a[m]==k || r-l<=0)break;
			if(a[m]<k)l=m+1;
			if(a[m]>k)r=m-1;
		}
		printf("%d\n",cnt);
	}
	return 0;
}

C++: #define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
const double EPS = 1e-10;

signed main() {
	int n;
	while (cin >> n, n) {
		vector<int>v(n); rep(i, 0, n)cin >> v[i];
		int k; cin >> k;
		int ans(0);
		int l = 0, r = n;
		while (l<r) {
			int mid = (l + r) / 2;
			ans++;
			if (v[mid] == k)break;
			else if (v[mid] < k) l = mid + 1;
			else r = mid;
		}
		cout << ans+(l==r) << endl;
	}
	return 0;
}

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

int main() {
    int N;
    while (cin >> N, N) {
        vector<int> v(N);
        for (auto& i : v) cin >> i;

        int x;
        cin >> x;
        int l = 0, r = N - 1;

        int count = 0;
        while (true) {
            int m = (r + l) / 2;
            count++;
            if (v[m] == x) break;
            if (l == r) break;

            if (v[m] < x) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        cout << count << endl;
    }

    return 0;
}

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

int main()
{
  int n, i;
  int m;
  int left, right, count;
  vector<int> v;
  while (cin>>n, n) {
    v.clear();
    v.resize(n);
    for (i = 0; i < n; i++) cin>>v[i];

    cin>>m;
    count = 1;
    left = 0;
    right = n-1;
    while (left < right) {
      count ++;
      if (v[(right-left)/2+left] > m) right = (right-left)/2+left-1;
      else if (v[(right-left)/2+left] < m) left = (right-left)/2+left+1;
      else {
	left = right = (right-left)/2+left;
	count--;
      }
    }
    cout<<count<<endl;
  }

  return 0;
}

C++: #include <iostream>

using namespace std;

#define MAX_N 101

int a[MAX_N];

int main() {
    int n, f;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> f;
        int count = 0;
        int r = 0, l = n-1;
        int mid;
        while (true) {
            mid = (r+l) / 2;
            count++;
            if (a[mid] == f) {
                 break;
            }
            if (l == r) {
                break;
            }
            if (a[mid] < f) {
                r = mid+1;
            }
            if (a[mid] > f) {
                l = mid-1;
            } 
        }
        cout << count << endl;
    }
    return 0;
}