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;
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 < r){
			int med = (l+r)/2;
			if(array[med] > M)r = med-1;
			else l = med+1;
			cnt++;
		}
		printf("%d\n",cnt);
	}
    return 0;
}

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

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

C++: #define _USE_MATH_DEFINES
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int N;
	while(cin >> N, N){
		int A[100], Target;
		for(int i = 0; i < N; i++) cin >> A[i];
		cin >> Target;

		int l = 0, r = N - 1, piv;
		int cnt = 0;
		while(r - l > 0){
			cnt++;
			int mid = (l + r)/2;
			if(A[mid] > Target) r = mid - 1;
			else if(A[mid] < Target) l = mid + 1;
			else{
				cnt++; break;
			}
		}
		printf("\t%d\n", cnt);
	}
	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;
  //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;
    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 main(){
	int num[101],r,l,c;
	int kazu, target, t;
	int i;

	while (1){
		t = 0;
		cin >> kazu;

		if (kazu == 0){
			break;
		}

		for (i = 0; i < kazu; i++){
			cin >> num[i];
		}

		cin >> target;


		l = 0;
		r = (kazu - 1);
		t = 0;
		while (r>=l){
			c = (l + r) / 2;
			t++;
			if (num[c] == target){
				break;
			}else if (r<=l){
				break;
			}else if(num[c] < target){
				l = c + 1;
			}else{
				r = c - 1;
			}
			
		}


		cout << t << endl;
	}

}

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

void a_reset(int a[]){
	for(int i = 0;i<150;i++){
		a[i] = 0;
	}
}
int nibn(int a[], int s, int e, int k);
int nibn(int a[], int s, int e, int k){
	if(s>e) return 1;
	if(s == e && a[s] != k){
		return 1;
	}
	if(a[(s+e)/2] == k){
		return 1;
	}
	else if(a[(s+e)/2] < k){
		return 1 + nibn(a,(s+e)/2+1,e,k);
	}
	else if(a[(s+e)/2] > k){
		return 1 + nibn(a,s,(s+e)/2,k);
	}
}


int main(){
	int n, a[150], ans, k;
	while(cin >> n){
		if(!n) break;
		ans = 0;
		a_reset(a);
		for(int i = 0;i<n;i++){
			cin >> a[i];
		}
		cin >> k;
		cout << nibn(a,0,n,k) << endl;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,string> P;
#define INF (1<<20)

int main(){
  int n;
  int num[1111];
  while(cin >> n, n){
    for(int i=0;i<n;i++){
      cin >> num[i];
    }
    sort(num,num+n);
    int tar; cin >> tar;
    int cnt = 0;
    int left = 0;
    int right = n-1;
    while(left < right){
      int mid = (left+right)/2;
      if(num[mid] == tar) break;
      else if(num[mid] > tar) right = mid - 1;
      else left = mid + 1;
      cnt++;
    }
    cout << cnt+1 << endl;
  }
}

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

std::vector<int> v;

int main()
{
	int n;
	while( std::cin >> n, n )
	{
		v.clear();

		for( int i = 0; i != n; ++i )
		{
			int a;
			std::cin >> a;
			v.push_back( a );
		}

		int b;
		std::cin >> b;

		int ans = 1;
		int l = 0, r = v.size() - 1;
		while( l != r )
		{
			int mid = ( l + r ) / 2;
			
			if( v[mid] < b )
				l = mid + 1;
			else if( v[mid] > b )
				r = mid - 1;

			++ans;
		}

		std::cout << ans << std::endl;
	}

	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int main()
{
	int n;
	while (scanf("%d", &n), n)
	{
		int d[100];
		for (int i = 0; i <= n; ++i)
			scanf("%d", d + i);

		int l = 0;
		int u = n-1;
		int ans = 0;
		while (l <= u)
		{
			++ans;
			int m = (l + u) / 2;
			if (d[m] == d[n])
				break;
			else if (d[m] > d[n])
				u = m - 1;
			else
				l = m + 1;
		}
		printf("%d\n", ans);
	}

	return 0;
}

C++: #include<cstdio>
#include<iostream>
using namespace std;
int main(){
	int n,s;
	int a[101];
	while(cin >> n){
		if(n == 0)break;
		for(int i = 0; i < n; i++) cin >> a[i];
		cin >> s;

		int left = 0,right = n-1;
		int cnt = 0;
		while(1){
			if(left > right)break;
			int mid = (left + right) / 2;
			cnt++;
			if(a[mid] == s){
				break;
			}
			else if(a[mid] < s){
				left = mid + 1;
			}
			else
				right = mid - 1;
		}
		printf("%d\n",cnt);
	}
	return 0;
}

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

int main()
{
  int n;
  while( cin >> n, n ) {
    int target;
    int cnt = 0;
    int l = 0, r = n-1, m = (l+r) / 2;
    int data[100001];
   
    for(int i=0; i<n; i++) cin >> data[i];
    cin >> target;
    
   

    while( target != data[m] && l <= r ) {
      m = (l+r) / 2;
      if( target > data[m] ) l = m+1;
      else r = m-1;
      cnt++;
    }

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