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 <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

//common
typedef int  i32;
typedef long long i64,ll;
#define BR "\n"

#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

//config
#define MODE_DEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef MODE_DEBUG
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl

#define  DUMP(x)  cerr << #x << " = " << (x) <<endl
#define DEBUG(x) DUMP(x) << " (L" << __LINE__ << ")" << " " << __FILE__<<endl
#define CHECK(exp,act)  if(exp!=act){DUMP(exp);DEBUG(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#else
#define DUMP(x)
#define DEBUG(x)
#define CHECK(exp,act)
#define STOP(e)
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}
template<class T> inline string toString(const vector<vector<T>>& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}

int main(){
	while(true){
		int N;cin >> N;
		if(N==0)break;
		vector<int> as(N);	

		REP(i,N)cin >>as[i];

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

		int c=0;
		while(r>l){
			// DUMP(l);
			// DUMP(r);
			c++;
			int m=(l+r)/2;
			if(as[m]<v){
				l=m+1;
			}else if(as[m]>v){
				r=m-1;
			}else{
				break;
			}
		}
		cout<< (c+1)<<endl;
	}

	return 0;
}

C++: #include <iostream>
#include <vector>
using namespace std;
 
int main(){
	int n,t,c;
	int mid,high,low,key;
	vector<int> d;
	while(cin >> n && n){
		d.clear();c=0;
 
		for(int i=0;i<n;i++){
			cin >> t;
			d.push_back(t);
		}
 
		cin >> key;
		low=0;high=n-1;	
		do{
			mid=(low+high)/2;
 
			if(d[mid] < key)
				low = mid+1;
			else if(d[mid] > key)
				high = mid-1;
			c++;
		}while(key != d[mid] && mid !=high && mid !=low);
 
		cout << c << endl;
	}
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,s;
  while(cin >> n&&n){
    ll tar;
    vary(int,v,n,0);
    rep(i,n){
      cin >> v[i];
    }
    cin >> tar;
    int lb = 0,ub = n-1;
    int ans = 0;
    while(1){
      int mid = (lb+ub)/2;
      ++ans;
      if(mid == ub){
        break;
      }
      if( tar == v[mid]) break;
      if(v[mid] < tar){
        lb = mid+1;
      }
      else{
        ub = mid-1;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main(){
	int *data, n, key, count, p, l, c;
	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::sort(data, data+n);
		std::cin >> key;
		p=0, l=n-1,count = 1;
		while(true){
			if(p>l)
				break;
			c = (p+l)/2;
			if(data[c] == key && p==l)
				break;
			if(data[c] > key)
				p = c+1;
			else
				l = c-1;
			count++;
		}
		std::cout << count << std::endl;
		delete[] data;
	}
}

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

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

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;
        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 <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;
    }
  }
  cout<<res<<endl;
}

int main (int argc, char const* argv[]) {
  while (cin>>n, n) {
    solve();
  }
  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 p,l=0,r=n-1,t=0;
    cin>>p;
    while(l<=r){
      t++;
      int mid=(l+r)/2;
      if(a[mid]==p)break;
      if(a[mid]>p)r=mid-1;
      else l=mid+1;
    }
    cout<<t<<endl;
  }
}