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<iostream>
#include<cstdio>
#include<vector>
using namespace std;

int main() {
	int a;
	while (cin>>a,a)
	{
		int b[100];
		for (int c = 0; c < a; c++)scanf("%d", &b[c]);
		int d; cin >> d;
		int MIN = 0, MAX = a - 1;
		for (int i = 0; i < 100; i++) {
			if (MAX - MIN == 1) { cout << i + 2 << endl; break; }
			int k = (MIN + MAX) / 2;
			if (b[k] > d)MAX =k-1;
			else if (b[k] < d)MIN =k+1;
			else { cout << i + 1 << endl; break; }
		}
	}
}

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


int main(){
    int n, search;
    while (cin >> n && n){
	int inp[101];
	for (int i = 0; i < n; i++) cin >> inp[i];
	cin >> search;

	int *s = inp, *e = inp + n - 1, *p = inp + (n-1)/2;
	int ans = 0;
	int b = 0;
	while (1){
	    ans++;
	    if (p == s && p == e) break;
	    if (*p == search) break;
	    else if (*p > search){
		e = p-1;
		p = s + (e - s)/2;
	    }
	    else if (*p < search){
		s = p+1;
		p = s + (e - s)/2;
	    }
	}

	cout << ans << endl;
    }
}

C++: #include<iostream>
using namespace std;
int s[100],ans;
int ok(int c){
  if(s[c]==ans) return 1;
  else if(s[c]<ans) return 2;
  else if(s[c]>ans) return 3;
} 
int main(){
  int n,max,min,count;
  while(cin>>n){
    if(n==0) break;
    count=0;
    for(int i=0;i<n;i++) cin >> s[i];
    cin >> ans;
    min = 0;
    max = 6;
    while(1){
      count++;
      if(ok((min+max)/2)==1){
	cout << count << endl;
	break;
      }
      else if(ok((min+max)/2)==2) min=(min+max)/2+1;
      else max=(min+max)/2-1;
      if(max<min){
	cout << count << endl;
	break;
      }
    }
  }
  return 0;
}

C++: #include<iostream>
using namespace std;
int main(){
  while(true){
    int a[1000];
    int q;
    int n;
    bool found=false;
    int cmp = 0;
    cin >> n;
    if( n == 0 ) break;
    for(int i = 0; i < n; ++i){
      cin >> a[i];      
    }
    cin >> q;
    int l = 0;
    int r = n;
    int prem=-1;
    while(r-l>1){
      int m = (l+r)/2;
      //      if(prem==m)break;
      if(a[m]>q){
	++cmp;
	r=m;
      }else if(a[m]==q){
	++cmp;
	found=true;
	break;
      }else{
	++cmp;
	l=m;
      }
      prem=m;
    }
    if(!found)++cmp;
    cout << cmp << endl;
  }
  return 0;
}

C++: #include <stdio.h>
#include <stack>
#include <math.h>

using namespace std;

struct Info{
	int id,sum;
};

int main(){

   int n,k,table[100],left,right,count,m;

   while(true){
	   scanf("%d",&n);
	   if(n == 0)break;

	   for(int i=0; i < n; i++)scanf("%d",&table[i]);

	   scanf("%d",&k);

	   count = 0;
	   left = 0,right = n;
	   m = (left+right)/2;
	   while(true){
		   count++;
		   if(table[m] == k)break;
		   else{
			   if(right-left==1){
				   if(right <= n && table[right] == k)count++;
				   break;
			   }
			   if(table[m] < k){
				   left = m;
				   m = (left+right)/2;
			   }else{
				   right = m;
				   m = (left+right)/2;
			   }
		   }
	   }

	   printf("%d\n",count);

   }

    return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, ans, a[1000], res;

int main(){
	while (cin >> n&&n){
		res = 0;
		fill(a, a + 1000, 0);
		REP(i, n)cin >> a[i];
		cin >> ans;
		int lb = -1, ub = n;
		while (ub - lb > 1){
			/*cout << ub << " " << lb << endl;*/
			int mid = (ub + lb) / 2;
			if (a[mid] < ans){
				lb = mid;
				res++;
			}
			else if (a[mid] > ans){
				ub = mid;
				res++;
			}
			else{
				res++;
				break;
			}
		}
		cout << res << endl;
	}
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define INF 1<<30

int main() {
  int n;
  while(cin >> n, n) {
    vector<int> v(n);
    REP(i,n)
      cin >> v[i];
    int a;
    cin >> a;

    sort(ALL(v));
    int lb = 0, ub = n;
    int res = 0;
    while(ub-lb>1) { // ツつアツつアツづ債適ツ督鳴づ可。
      int mid = (lb+ub)/2;
      if (v[mid] <= a) lb = mid;       // ツ催渉ャツ値ツづーツ仰づ淞づゥツづ按づァlbツづbツづーツ禿シツづェツ妥鳴つヲツづゥ
      else ub = mid;
      ++res;
    }
    if (v[lb] != a)
      ++res;
    cout << res << endl;
  }
}

C++: #include<iostream>
using namespace std;
int s[100],ans;
int ok(int c){
  if(s[c]==ans) return 1;
  else if(s[c]<ans) return 2;
  else if(s[c]>ans) return 3;
} 
int main(){
  int n,max,min,count;
  while(cin>>n){
    //cout << n << endl;
    if(n==0) break;
    count=0;
    for(int i=0;i<n;i++) cin >> s[i];
    cin >> ans;
    min = 0;
    max = 6;
    while(1){
      count++;
      if(ok((min+max)/2)==1||min==max){
	cout << count << endl;
	break;
      }
      else if(ok((min+max)/2)==2) min = (min+max)/2 + 1;
      else max = (min+max)/2 - 1;
    }
  }
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef pair<int,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
	int N;
	while(scanf("%d",&N),N){
		int array[128];
		rep(i,N){
			scanf("%d",&array[i]);
		}
		int M;
		scanf("%d",&M);
		int l = 0;
		int r = N-1;
		int cnt = 1;
		while(l+1 != r){
			int med = (l+r)/2;
		//	printf("%d ",array[med]);
			if(array[med] == M)break;
			if(array[med] > M)r = med-1;
			else l = med+1;
			cnt++;
		}
		//puts("");
		printf("%d\n",cnt);
	}
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin>>n,n){
  int a[n];
  for (int i=0;i<n;++i){
    cin>>a[i];
  }
  
  int goal;
  cin>>goal;
  int left,right;
  
  left=0;
  right=n;
  if(a[n/2]==goal){
    cout<<1<<endl;
    continue;
  }
  int sum=1;
  while(left<right){
    if( a[(left+right)/2]==goal ){
++sum;
break;
}
    if(a[(left+right)/2]>goal){right=(left+right)/2;}
    if(a[(left+right)/2]<goal){left=(left+right)/2+1;}
    sum++;
  }
  //if(left==right){
    cout<<sum<<endl;
    //}
  
  
 }
 return 0;
}