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++: #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(true){
			cnt++;
			if(r - l <= 0) break;
			int mid = (l + r)/2;
			if(A[mid] > Target) r = mid - 1;
			else if(A[mid] < Target) l = mid + 1;
			else break;
		}
		printf("\t%d\n", cnt);
	}
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>

using namespace std;


int main(){

	int n;
	while(1){
		cin>>n;if(n==0)break;
		int P[105]={};
		for(int i=0;i<n;i++){
			cin>>P[i];}

		sort(P,P+n);
		int C=0;
		int x;
		cin>>x;
		int H=(n-1)/2;
		int L=n-1,S=0;
		while(1){
			//cout<<L<<" "<<S<<endl;
			if (L==S){
				//cout<<"%";
				C++;break;
			}
			if (P[H]==x){C++;break;}

			else if(P[H]<x){S=H+1;
			H=(S+L)/2;C++;//cout<<"#";//cout<<H<<endl;//break;
			}
			else if(P[H]>x){L=H-1;
				H=(S+L)/2;C++;//cout<<"$";//cout<<H;//break;
			}
			
		}
		cout<<C<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

using namespace std;

#define all(c) c.begin(),c.end()
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

typedef long long ll;
typedef vector<int> vi;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& val){
    os << "[ ";
    for(typename vector<T>::const_iterator it=val.begin();
        it != val.end();++it){
        os << *it << " ";
    }
    os << "]";
    return os;
}

int solve(const vi& d,int f){
    int N = d.size();
    int head = 0;
    int tail = N-1;
    int ret = 0;
    // debug(d);
    // debug(f);
    while(true){
        int mid = (head + tail) / 2;
        ret++;
        // debug(mid);
        // debug(d[mid]);
        // debug(ret);
        if(d[mid] == f){
            // debug(d[mid]);
            return ret;
        }else if(d[mid] < f){
            head = mid + 1;
        }else if(d[mid] > f){
            tail = mid - 1;
        }
        if(head > tail){
            return ret;
        }
    }
    return -1;
}

int main(){
    while(true){
        int n;
        cin >> n;
        if(n == 0) break;
        vi d(n);
        rep(i,n) cin >> d[i];
        int f;
        cin >> f;
        cout << solve(d,f) << endl;
    }
    return 0;
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,s;
  while(cin >> n&&n){
    vary(int,v,n+1,0);
    rep(i,n+1){
      cin >> v[i];
    }
    int lb = 0,ub = n-1;
    int ans = 0;
    while(1){
      int mid = (lb+ub)/2;
//       debug(v[mid]);
      ++ans;
      if(mid == ub || v[n] == v[mid]){
        break;
      }
      if(v[mid] < v[n]){
        lb = mid+1;
      }
      else{
        ub = mid-1;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

C++: #include <cstdio>
 
int main()
{
    int n,key;
 
    while (scanf("%d", &n), n) {
	int a[n];
	for (int i = 0; i < n; i++) {
	    scanf("%d", a + i);
	}
 
	scanf("%d", &key);
 
	int lb = 0, ub = n-1, cnt = 0;
	while (ub - lb >= 0) {
	    int mid = (lb + ub) / 2;
	    cnt++;
 
	    if (key == a[mid]) {
		break;
	    }
	    if (key < a[mid]) {
		ub = mid - 1;
	    } else {
		lb = mid + 1;
	    }
	}   
	printf("%d\n", cnt);
    }
    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 {
			count = count + 2;
			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 <vector>
#include <algorithm>

using namespace std;

int main(){

	int n;
	while(cin>>n&&n!=0){
		vector<int> nums;
		int t;
		for(int i = 0; i < n; i++){
			cin>>t;
			nums.push_back(t);
		}
		int s;
		cin>>s;
		int ub=n-1;
		int lb=0;
		int cnt=0;
		while(1){
			if(lb<0||ub<0||ub>=n||lb>=n)
				break;
			int mid=ub+lb;
			mid/=2;
			cnt++;
			if(nums[mid]==s||ub==lb){
				break;
			}
			else if(nums[mid]>s){
				ub=mid-1;
			}
			else if(nums[mid]<s){
				lb=mid+1;
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}