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;
		int cnt = 0;
		while(l < r){
			int med = (l+r-1)/2;
			if(array[med] > M)r = med;
			else l = med+1;
			cnt++;
		}
		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 = 1;
    int l = 0, r = n-1, m;
    int data[100001];
   
    for(int i=0; i<n; i++) cin >> data[i];
    cin >> target;
    
   

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

    cout << cnt << endl;
  }

}

C++: #include <stdio.h>

int main()
{
        int n, i, start, end;
        int data[100];
        int search;
        int count;
        int center;
     while (scanf("%d", &n) && n != 0) {
                for (i = 0; i < n; i++) {
                        scanf("%d", &data[i]);
                }
                scanf("%d", &search);
                start = 0;
                end = n-1;
                count = 0;
                while (start <= end) {
                  center = (start+end)/2;
                  count++;
                  if (search > data[center]) {
                    start = center+1;
                  }  else if (search < data[center]){
                    end = center-1;
                  } else if (search == data[center])
                         break;
                }
                printf("%d\n", count);
        }
        return 0;
}

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

using namespace std;

int SearchCount(vector<int>, int);

int main(){
  int i, n, m, Search, Count;
  vector<int> data;

  while(1){
    cin >> n;
    if(n == 0) break;

    for(i=0; i<n; ++i){
      cin >> m;
      data.push_back(m);
    }
    cin >> Search;

    Count = SearchCount(data, Search);
    cout << Count << endl;
    data.clear();
  }

  return 0;
}

int SearchCount(vector<int> data, int Search){
  int middle, left = 0, right = data.size()-1, count=0;

  while(right >= left){
    middle = (left + right)/2;
    count++;
    if(Search == data[middle]){
      break;
    }else if(Search < data[middle]){
      right = middle-1;
    }else{
      left = middle+1;
    }      
  }
  return count;

}

C++: #include <iostream>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
int A[100];
int main() {
  while(true) {
    int N; cin >> N;
    if(N == 0) break;
    REP(i,N) cin >> A[i];
    int t; cin >> t;
    int lb = 0, ub = N - 1;
    int c = 0;
    while(ub >= lb) {
      int mid = (lb + ub) / 2;
      //DEBUG(lb);
      //DEBUG(ub);
      //DEBUG(mid);
      ++c;
      if(A[mid] == t) {
        break;
      }
      if(t < A[mid]) {
        ub = mid - 1;
      }
      else {
        lb = mid + 1;
      }
    }
    cout << c << endl;
  }
}

C++: #define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 29;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;
const int CLK = CLOCKS_PER_SEC;

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)

int nums[100];

int main(){
	int n, p;
	while(cin >> n && n){
		rep(i, n){
			cin >> nums[i];
		}
		cin >> p;
		int l = 0, r = n;
		int res = 0;
		while(r - l > 1){
			res++;
			int mb = (l + r) / 2;
			if(nums[mb]==p) break;
			else if(nums[mb] < p) r = mb;
			else l = mb;
		}
		cout << res + 1 << 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; )
	{
		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 <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 = 0, l = n-1;
        int mid;
        while (true) {
            mid = (r+l) / 2;
            count++;
            if (a[mid] == f) {
                 break;
            }
            if (l == r + 1) {
                count++;
                break;
            }
            if (l == r) {
                break;
            }
            if (a[mid] < f) {
                r = mid+1;
            }
            if (a[mid] > f) {
                l = mid-1;
            } 
        }
        cout << count << endl;
    }
    return 0;
}