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;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> P;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };


int main() {
	int n;
	while ( ~scanf( "%d", &n ) && n ) {
		int s = 0, e = n - 1, f;
		int ans = 0;
		int num;
		VI a( n );
		for ( int i = 0; i < n; i++ ) {
			scanf( "%d", &a[ i ] );
		}
		sort( a.begin(), a.end() );

		scanf( "%d", &num );
		while ( s <= e ) {
			ans++;
			f = s + e / 2;
			if ( a[ f ] == num ) {
				break;
			}
			else if ( a[ f ] < num ) {
				s = f + 1;
			}
			else if ( a[ f ] > num ) {
				e = f - 1;
			}
		}
		printf( "%d\n", ans );
	}
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stdexcept>
#include<cmath>
#include<memory>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<deque>
#include<sstream>
#include<iomanip>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<map>
#include<set>
#include<list>
#include<cassert>
#include<deque>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<27
#define all(n) n.begin(),n.end()
#define insert(a,b,c,d) PP(P(a,b),P(c,d))
#define F first
#define S second
#define pb push_back
#define pf push_front
#define LIM 100000
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef long long ll;
typedef unsigned long long ull;

int main(){

  while(true){
    int n;
    cin >> n;
    if(n == 0)break;
    vector<int> vec;
    rep(i,n){
      int in; cin >> in;
      vec.pb(in);
    }
    int key,cnt = 0;
    cin >> key;
    int l,r,m;
    l = 0,r = n-1;
    while(l <= r){
      m = (l+r)/2;
      cnt++;
      if(vec[m] == key)break;
      if(vec[m] > key)r = m;
      else l = m+1;
    }
    cout << cnt << 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)
		return count;
	else if(p>l)
		return count-1;
	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>
using namespace std;

int main()
{
  int n;
  for(;cin>>n,n;)
    {
      int data[n];
      for(int i=0;i<n;i++)
	{
	  cin>>data[i];
	}
      int s;
      cin>>s;
      int hi=0,lo=n-1;
      int cnt=0;
      while(true)
	{
	  int p = (hi+lo)/2;

	  //	  cout<<"HI:"<<hi<<" LO:"<<lo<<" "<<cnt<<endl;
	  //	  cout<<"data[p]:"<<data[p]<<" s:"<<s<<endl;
	  if(hi>lo)
	    break;
	  cnt++;
	  if(data[p]==s)
	      break;
	  else if(data[p]<s)
	    hi=p+1;
	  else
	    lo=p-1;
	}
      cout<<cnt<<endl;
    }
}

C++: #include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int n;
	cin >> n;
	vector<int> a(n);
	if(n == 0) break;
	REP(i,n) cin >> a[i];
	int num;
	cin >> num;
	int l,m,h,ans;
	h = n;
	l = 0;
	m = (h+l)/2;
	ans = 0;
	while(true){
	    if(a[m] > num){
		if(h-l == 1){
		    ans++;
		    break;
		}
		h = m;
	    }else if (a[m] < num){
		if(h-l == 1){
		    ans++;
		    break;
		}
		l = m;
	    }else{
		ans++;
		break;
	    }
	    m = (h+l)/2;
	    ans++;
	}
	cout << ans << 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 = 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) {
      if (mid != ub) lb = mid + 1;
      else lb = mid;
    }
    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>
using namespace std;

int bin_search(int x[],int size,int key)
{
	int low = 0,high = size-1;
	int count=1;
	while(low < high){
		int mid = (low+high)/2;
		if(x[mid] == key)
			return count;
		else if(x[mid] > key)
			high = mid-1;
		else
			low = mid+1;
		count++;
	}
	return count;
}
int main()
{
	int size;
	int key;
	int x[101];
	while(cin >> size){
		if(size == 0)
			break;
		for(int i=0;i<size;i++){
			cin >> x[i];
		}
		cin >> key;
		cout << bin_search(x,size,key) << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n;
	while(cin >> n , n){
		int need , ans = 0;
		vector<int> d(n);
		rep(i,n) cin >> d[i];
		
		cin >> need;
		int l = 0 , r = n-1;
		while( l < r ){
			ans++;
			int m = (l+r)/2;
			if(d[m] > need) r = m-1;
			else if(d[m] < need) l = m+1;
			else {break;}
		}
		cout << ans+1 << endl;
	}
}

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;
}