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 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;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

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

void search(int times);
void twice(int data[],int t, int target, int count);

void search(int times){
	int data[times-1] = {0};
	int target, count=0;
	for(int i=0;i<times-1;i++){
		cin >> data[i];
	}
	cin >> target;
	

	return twice(data, times-1, target, count);
}

void twice(int data[],int t, int target, int count){
	
	if(t == 1 || t == 0){
		count++;
		cout << count <<endl;
	} else {

	
	int times = t/2;
	if(data[times] < target){
		int dataN[times] = {};
		for(int i=0;i<times;i++){
			if(t % 2 == 1){
				dataN[i]=data[i+times+1];
			} else if(t % 2 == 0){
				dataN[i] = data[i+times];
			}
		}

		count++;
		twice(dataN,times, target, count);

	} else if(data[times] > target){
		int dataN[times] = {};
		for(int i=0;i<times;i++){
			dataN[i]=data[i];
		}
		count++;
		twice(dataN,times, target, count);
	} else if(data[times] == target){
		cout << count << endl;
	}
}
}

int main() {
	int i;
	while(1) {
		cin >> i;
		//cout << res << endl;
		if(i == 0){
			break;
		}

		search(i+1);
	}
	return 0;
}

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

int T[100010];
int find(int m,int x){
	int r=0,l=m-1,ans=0;
	while(1){
		ans++;
		if(T[(r+l)/2]==x)return ans;
		else if(r==l)break;
		if(T[(r+l)/2]>x)l=(r+l)/2;
		else if(T[(r+l)/2]<x)r=(r+l)/2+1;
	}
	return ans;
}
int main(){
	int n,k,num,ans;
	while(1){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>T[i];
		}
		cin>>k;
		ans=find(n,k);
		cout<<ans<<endl;
	}
	return 0;
}

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

int main() {
  int hi,lo,m,n,a,i,k,d[100];
  while(cin >> n && n!=0) {
	  for (i=0;i<n;i++) cin >> d[i];
	  cin >> a;
	  hi=n-1; lo=k=0;
	  while(hi>=lo) {
	  k++; m=(hi+lo)/2; 
	  if (d[m]<a) lo=m+1; else if (d[m]>a) hi=m-1; else break;
	  if (hi==lo) { k++; break;}
	   }
	  cout << k << 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 = (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<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];
    }
    int tar; cin >> tar;
    int cnt = 0;
    int left = 0;
    int right = n-1;
    while(left <= right){
      int mid = (left+right)/2;
      cnt++;
      if(num[mid] == tar) break;
      else if(num[mid] > tar) right = mid - 1;
      else left = mid + 1;
    }
    cout << cnt << endl;
  }
}

C++: #include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;


int N, M;
int solve(vector<int> &v){
  int l = -1, r = (int)(v.size()), res = 0;
  while(r - l > 1){
    ++res;
    int m = (r + l) / 2;
    if(v[m] >= M) r = m;
    else l = m;
  }
  return res;
}

int main() {
  while(cin >>N && N){
    vector<int> v(N);
    REP(i, N) cin >>v[i];
    cin >>M;
    cout <<solve(v) <<endl;
  }
  return 0;
}

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

C++: #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int main() {
	int n;
	int num[110];
	while(n=in()){
		int i;
		for(i=0;i<n;i++){
			cin>>num[i];
		}
		int g=in();
		int a=0,b=n-1;
		int res=0;
		while(res++,num[(a+b)/2]!=g){
//cout<<a<<" "<<b<<endl;
			if(num[(a+b)/2]>g)b=(a+b)/2-1;
			else a=(a+b)/2+1;
			if(a>b)break;
		}
		cout<<res<<endl;
	}
	return 0;
}

C++: #include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<numeric>
using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+8
#define EPS 1e-8
#define rep(i,j) for(int  i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < k; i++)
typedef long long ll;
typedef pair<int,int> Pii;
int main(){
        int n;
        scanf("%d",&n);
        int num[128];
        rep(i,n){
                scanf("%d",&num[i]);
        }
        int target;
        scanf("%d",&target);
        int l = 0;
        int r = n-1;
        int mid = (l+r)/2;
        int cnt = 1;
        while(num[mid] != target && mid > 0 && mid < n-1){
                cnt++;
                if(num[mid] > target)r = mid;
                else l = mid+1;
                mid = (l+r)/2;
        }
        printf("%d\n",cnt);
        return 0;
}