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 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 (1){
			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;

int main(){
    while(1){
        int n;
        cin >> n;

        if(n == 0)  break;

        int A[n];
        for(int i = 0; i < n; i++)  cin >> A[i];

        int x;
        cin >> x;
        int ans = 1;
        int r = n-1, l = 0;

        while(l < r){
            ans++;
            int mid = (r+l)/2;
            if(A[mid] == x || l == r) break;
            else if(A[mid] < x) l = mid+1;
            else if(A[mid] > x) r = mid-1;
        }

        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

int nibo(int, vector<int>);

int main(void) {
	int n;
	vector<int> ans;

	while(true) {	
		cin >> n;
		if (n == 0) {
			break;
		}
		vector<int> data(n + 1 , 0);
		for (int i = 0; i < n + 1; i++) {
			cin >> data[i]; 
		}
		cout << nibo(n, data) << endl;
	}
       
	return 0;

}

int nibo(int n, vector<int> data) {
	int times = 0;
	int right = n - 1;
	int left = 0;
	int mid;
	int target = data[n];
	while((right - left) >= 0) {
		times++;
		mid = (right + left) / 2;
		if (data[mid] == target) {
			break;
		}
		if (data[mid] < target) {
			left = mid + 1;
		}
		if (data[mid] > target) {
			right = mid - 1;
		}
	}
	return times;
}

C++: #include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

//common
typedef int  i32;
typedef long long i64,ll;
#define BR "\n"

#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

//config
#define MODE_DEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef MODE_DEBUG
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl

#define  DUMP(x)  cerr << #x << " = " << (x) <<endl
#define DEBUG(x) DUMP(x) << " (L" << __LINE__ << ")" << " " << __FILE__<<endl
#define CHECK(exp,act)  if(exp!=act){DUMP(exp);DEBUG(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#else
#define DUMP(x)
#define DEBUG(x)
#define CHECK(exp,act)
#define STOP(e)
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}
template<class T> inline string toString(const vector<vector<T>>& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}

int main(){
	while(true){
		int N;cin >> N;
		if(N==0)break;
		vector<int> as(N);	

		REP(i,N)cin >>as[i];

		int v;cin >> v;
		int l=0,r=N-1;

		int c=0;
		while(r>l){
			// DUMP(l);
			// DUMP(r);
			c++;
			int m=(l+r)/2;
			if(as[m]<v){
				l=m+1;
			}else if(as[m]>v){
				r=m-1;
			}else{
				break;
			}
		}
		cout<< (c+1)<<endl;
	}

	return 0;
}

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

int main()
{
  int n, i;
  int m;
  int left, right, count;
  vector<int> v;
  while (cin>>n, n) {
    v.clear();
    v.resize(n);
    for (i = 0; i < n; i++) cin>>v[i];

    cin>>m;
    count = 1;
    left = 0;
    right = n;
    while (left < right) {
      count ++;
      if (v[(right-left)/2+left] < m) right = (right-left)/2+left-1;
      else if (v[(right-left)/2+left] > m) left = (right-left)/2+left+1;
      else left = right = (right-left)/2+left;
    }
    cout<<count<<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 if(t == 2){
		if(data[0] == target || data[1] == target){
			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){
		count++;
		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 <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

int N, A[100], V;

int count(int first, int last){
    if(first > last){return 0;}

    int mid = (first + last) / 2;
    if(A[mid] == V){
        return 1;
    }else if(A[mid] > V){
        return 1 + count(first, mid-1);
    }else{
        return 1 + count(mid+1, last);
    }
}

int main(){
    while(std::cin >> N, N){
        REP(i, N){
            std::cin >> A[i];
        }

        std::cin >> V;
        std::cout << count(0, N-1) << std::endl;
    }
}

C++: #include<iostream>
#include<vector>
using namespace std;
int bs(int l,int r, int ans);
vector<int> lot;
int n,x;
int main(){
  while(cin >>n,n){
    lot.clear();
    for(int i=0,a; i<n; i++){cin >>a;lot.push_back(a);}
    cin >>x;
    cout <<bs(0,n-1,0)<<endl;
  }
  return 0;
}
int bs(int l, int r, int ans){
  int mid = (l+r)/2;
  if(l>r) return ans;
  if(lot[mid] == x) return ans+1;
  if(lot[mid] > x) return bs(l,mid-1,ans+1);
  return bs(mid+1,r,ans+1);
}