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 <algorithm>

using namespace std;

int s[100010],t[50010];
int n, q, ans = 0;

bool binary_search(int x) {
	int l = 0, r = n-1;
	ans = 0;
	while (r - l >= 1) {
		int m = (l + r) / 2;
		ans++;
		if (s[m] == x)return true;
		else if (s[m] > x) {
			r = m;
		}
		else if (s[m] < x) {
			l = m+1;
		}
	}
	ans++;
	return false;
}
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) {
			cin >> s[i];
		}
		cin >> t[0];
		binary_search(t[0]);
		for (int i = 0; i < n; i++) {
			s[i] = 0;
		}
			cout << ans << endl;
	}
	return 0;
}

C++: #include <iostream>

using namespace std;
int a[1000];

int bin_search(int m, int n, int k,int count) {
  int l = (m + n) / 2;
  if ( n < m) {
    return count;
  }
  count ++;
  if ( a[l] < k ) {
    return bin_search(l + 1, n, k, count);
  } else if ( a[l] > k ){
    return bin_search(m,  l - 1, k, count);
  }
  return count;
}

int main() {
  while (1) {
    int n;
    int k;
    cin >> n;
    if (n == 0) {
      return 0;
    }
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    cin >> k;

    int r = bin_search(0, n - 1, k,0);
    cout << r << endl;
  }
}

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

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

C++: #include<stdio.h>

int main(void)
{
	int x[100]={0};
	int st,fn,a,n,i,ty,kai;
	while(0==0){
		scanf("%d",&n);
		if(n==0)break;		
		kai=1;  st=0; fn=n-1;
		for(i=0;i<n;i++) scanf("%d",&x[i]);
		scanf("%d",&a);
		while(a!=x[ty]||fn-st>0){
			ty=(st+fn)/2;
		    if(a>x[ty])  st=ty+1;
			else fn= ty-1;
			kai++;
		}
		printf("%d\n",kai);
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int main(){
long n,a[100],b,s,m,e,i,j;
while(cin>>n){
if(n==0)break;
for(i=0;i<n;i++)cin>>a[i];
cin>>b;
s=0;e=n-1;
for(j=1;;j++){
m=(s+e)/2;
if(a[m]==b)break;
else if(a[m]<b)s=m+1;
else e=m-1;
if(e<s)break;
}
cout<<j<<endl;
}
return 0;
}

C++: #include<stdio.h>
int main()
{
	int n,i,a[100],l,m,r,x,c;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;++i)scanf("%d",&a[i]);
		scanf("%d",&x);
		for(c=1,l=0,r=n;l<r;++c)
		{
			m=(l+r)/2;
			if(a[m]==x)break;
			else if(a[m]<x) l=m+1;
			else r=m;
		}
		printf("%d\n",c);
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  while(true){
    int n;
    cin >> n;
    if(n == 0){
      break;
    }
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
      cin >> a[i];
    }
    int t;
    cin >> t;
    int ans = 0;
    int left = 0, right = n - 1;
    while(left <= right){
      ++ans;
      int mid = (left + right) / 2;
      if(a[mid] == t){
	break;
      }
      if(a[mid] > t){
	right = mid - 1;
      }
      else{
	left = mid + 1;
      }       
    }
    cout << ans << endl;
  }
  return 0;
}

C++: #include<iostream>
using namespace std;
int a[100];
int main(){
	int n,key;
	while(true){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++)cin>>a[i];
		cin>>key;
		int ans=0;
		int left=0,right=n-1,mid;
		while(true){
			if(left>right)break;
			mid=(left+right)/2;
			ans++;
			if(a[mid]==key)break;
			if(a[mid]<key)left=mid+1;
			if(a[mid]>key)right=mid-1;
		}
		cout<<ans<<endl;
	}
	return 0;
}

C++: #include <iostream>

using namespace std;

#define MAX_N 101

int a[MAX_N];

int main() {
    int n, f;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> f;
        int count = 0;
        int r = n-1, l = 0;
        int mid;
        while (true) {
            mid = (r+l) / 2;
            if (r < l) break;
            count++;
            if (a[mid] == f) {
                 break;
            }
            if (r == l) break;
            if (a[mid] < f) {
                l = mid+1;
            }
            if (a[mid] > f) {
                r = mid-1;
            } 
        }
        cout << count << endl;
    }
    return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
    for(int n; cin >> n && n; )
	{
		int target, ans = 0;
		vint v(n);
		
		rep(i, n) cin >> v[i];
		
		cin >> target;
		
		for(int lb = 0, ub = n - 1; lb <= ub; ans++)
		{
			int mid = (ub + lb) / 2;
			if(v[mid] <  target) lb = mid + 1;
			if(v[mid] >  target) ub = mid - 1;
			if(v[mid] == target)
			{
				ans++;
				break;
			}
		}
		
		cout << ans << 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 <cstdio>
#include <algorithm>
using namespace std;
int n, x;
int a[100];
int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<n; i++) scanf("%d",&a[i]);
        sort(a, a+n);
        scanf("%d", &x);
        int lb=0, ub=n-1, res=0;
        while (ub-lb>1) {
            res++;
            int mid=(lb+ub)/2;
            if (a[mid]<x) {
                lb=mid;
            } else if (a[mid]>x) {
                ub=mid;
            } else {
                break;
            }
        }
        printf("%d\n",res+1);
    }
}