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>
using namespace std;

int binSearch( int*, int, int, int, int );

int main(){
	int n;	// number
	int s;	// search
	int data[100+1];
	while(1){
		cin >> n;
		if( n == 0 ) break;

		for( int i=1; i<=n; i++ ){
			cin >> data[i];
		}
		cin >> s;

		cout << binSearch( data, s, 1, n, 0 ) << endl;
	}
	return 0;
}

int binSearch( int *data, int s, int first, int last, int comp ){
	comp++;
	if( first >= last ){
		return comp;
	}
	int p = (first+last)/2;
	if( data[p] < s ){
		return binSearch( data, s, p+1, last, comp );
	}else if( data[p] > s ){
		return binSearch( data, s, first, p-1, comp );
	}else{
		return comp;
	}
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
#include <cmath>
#include <cstdio>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()

using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int num[101];
int main(void){
	int n;
	while(cin >> n, n){
		rep(i, n) cin >> num[i];
		int x;
		cin >> x;

		int lb = 0, ub = n-1;
		int ans = 0;
		while(1){
			int mid = (ub+lb)/2;
			ans++;
			if(ub == lb) break;
			if(num[mid] == x) break;
			if(num[mid] < x) lb = mid+1;
			else ub = mid-1;
		}

		cout << ans << endl;
	}

    return 0;
}

C++: #include<iostream>
#include<algorithm>

using namespace std;

const int MAX = 101;
int data[MAX];
int n;
int ans;
int wanted;

void solve(){
  int start = 0;
  int end = n-1;
  //sort(data,data+n);
  while(1){
    ans++;
    int now = (int)(start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start >= end) break;
    if(data[now] > wanted) end = now-1;
    else start=now+1;
  }
}

int main(){
  while(cin >> n && n){
    ans = 0;
    for(int i = 0; i < n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  return 0;
}

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

int find( int* a, int b, int e, int t )
{
	int m = ( b + e ) / 2;
	if( b > e ){
		return 1;
	}
	if( t < a[ m ] && m != b ){
		return 1 + find( a, b, m - 1, t );
	}
	if( t > a[ m ] && m != e ){
		return 1 + find( a, m + 1, e, t );
	}
	return 1;
}


int main()
{
	int n;
	while( cin >> n && n ){
		int a[ 100 ] = {0};
		for( int i = 0; i < n; ++i ){
			cin >> a[ i ];
		}
		int d;
		cin >> d;
		cout << find( a, 0, n - 1, d ) << endl;
	}

	return 0;
}

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 = 0;
  while (ub >= lb) {
    int mid = (ub+lb)/2;
    if (l[mid] == t) {res++; break;}
    if (l[mid] < t) {
      lb = mid + 1;
    }
    else  if (l[mid] > t) {
      if (mid != 0) ub = mid - 1;
    }
    res++;
  }

  cout<<res<<endl;
}

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

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
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;
		int i = 0;
		while(MIN-MAX!=1) {
			int k = floor(double(MIN + MAX) / (double)2);
			if (b[k] > d) { MAX = k - 1; i++; }
			else if (b[k] < d) { MIN = k + 1; i++; }
			else { i++; break; }
		}
		cout << i << endl;
	}
}

C++: #include <bits/stdc++.h>
#define INF 114514810
#define FOR(i, r, n) for(int i=(r); i<(n); i++) 
#define REP(i, n) FOR(i, (0), n)

using namespace std;

int n, d[103], x, ct = 0;

bool twei(int k){
	int lb = -1; int ub = n;
	while (ub - lb > 1){
		ct++;
		int mid = (lb + ub) / 2;
		if (d[mid] == k) return 1;
		else if (d[mid] > k) ub = mid;
		else lb = mid;
	}
	return 0;
}

int main(){
	while (true){
		cin >> n;
		if (!n) break;
		REP(i, n)
			cin >> d[i];
		cin >> x;
		twei(x);
		cout << ct << endl;
		x = ct = 0;
	}
}

C++: #include<iostream>
using namespace std;
int n,t[100],a,L,R,M,ans;
int main(){
  while(cin>>n&&n){
    for(int i=0;i<n;i++){
      cin>>t[i];
    }
    cin>>a;

    L=0;
    R=n;
    ans=0;
    while(L<R){
      M=(L+R)/2;
      if(t[M]==a){
	break;
      }else if(t[M]>a){
	R=M;
	ans++;
      }else{
	L=M+1;
	ans++;
      }
    }
    cout<<ans+1<<endl;
  }
  
  return 0;
}

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 = 0;
  while (1) {
    res++;
    if (ub == lb) {
      //printf("lb=%d ub=%d\n", lb, ub);
      break;
    }
    int md = (lb+ub)/2;
    //printf("lb=%d ub=%d md=%d\n", lb, ub, md);
    if (l[md] < t) {
      lb = md + 1;
    } else if (l[md] > t) {
      ub = md - 1;
    } else {
      res++; break;
    }
  }
  cout<<res<<endl;
}

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

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

int main(){
	int n;
	while( cin >> n, n ){
		int a[101], key;
		for(int i=0 ; i < n ; i++ ){
			cin >> a[i];
		}
		cin >> key;
		
		int low = 0, high = n, mid = -1, cnt = 0;
		while( true ){
			cnt++;
			mid = (low + high) / 2;
			
			if( a[mid] == key ){
				break;
			}else if( a[mid] < key ){
				if( low == mid ) break;
				low = mid;
			}else{
				if( high == mid ) break;
				high = mid;
			}
		}
		cout << cnt << endl;
	}
}

C++: #include<iostream>
#include<algorithm>

using namespace std;

const int MAX = 101;
int data[MAX];
int n;
int ans;
int wanted;

void solve(){
  int start = 0;
  int end = n-1;
  sort(data,data+n);
  while(1){
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start >= end) break;
    if(data[now] > wanted) end = now-1;
    else start=now+1;
  }
}

int main(){
  while(cin >> n && n){
    ans = 0;
    for(int i = 0; i < n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  return 0;
}

C++: 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,k;
  while(1){
    cin>>n;
    if(n==0)break;
    vi a(n);
    rep(i,n)cin>>a[i];
    cin>>k;
    int r=n-1;
    int l=0;
    rep(i,n){
      int mid=(r+l)/2;
      if(a[mid]==k){
	cout<<i+1<<endl;
	break;
      }
      if(a[mid]<k)l=mid+1;
      else r=mid-1;
      if(r<l){
        cout<<i+1<<endl;
        break;
      }
    }

  }
}