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>

int search(int *n, int key, int p, int l, int count){
	int c = (p+l)/2;
	int cnt = count+1;
	if(n[c] == key || p>l)
		return cnt;
	else if(n[c] > key)
		return search(n, key, c+1, l, cnt);
	else
		return search(n, key, p, c-1, cnt);
}

int main(){
	int *data, n, key, count, p, l, c;
	while(true){
		std::cin >> n;
		if(n==0)
			return 0;
		data = new int[n];
		for(int i=0; i<n; i++)
			std::cin >> data[i];
		std::cin >> key;
		std::cout << search(data, key, 0, n-1, 0) << std::endl;
		delete[] data;
	}
}

C++: #include<iostream>
using namespace std;
int a[200];
int n;

int search(int i){
  int count = 0;
  int lix = 0,rix = n - 1;
  while(lix <= rix){
    cout << lix << rix << endl;
    int med = (lix + rix)/2;

    count++;
    if(a[med] == i)return count;

    if(a[med] < i){
      lix = med + 1;
      continue;
    }

    if(a[med] > i){
      rix = med - 1;
      continue;
    }
  }
  return count;
}

int main(){

  while(true){
    cin >> n;
    if(n == 0)break;
    for(int i = 0;i < n;i++){
      cin >> a[i];
    }
      
    int i;
    cin >> i;
    cout << search(i) << endl; 
  }
}

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>
using namespace std;
int bin(int x,int a[],int n){
	int r=n-1,l=0,mid,k=0;
	while(r-l>=1){
		mid=(r+l)/2;
		if(a[mid]>x)
		r=mid-1;
		else l=mid+1;
		k++;
	}
	return k+1;
}
int main(){
	int n,x,a[1000];
	while(cin>>n,n){
		for(int i=0;i<n;i++)
		cin>>a[i];
		cin>>x;
		cout<<bin(x,a,n)<<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[lb]);
//       debug(v[mid]);
//       debug(v[ub]);
      ++ans;
      if(mid == ub || v[n] == v[mid]){
        break;
      }
      if(v[mid] < v[n]){
        lb = mid+1;
      }
      else{
        ub = mid;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

C++: #include<iostream>

int search(int *n, int key, int p, int l, int count){
	int c = (p+l)/2;
	if(n[c] == key || p>=l)
		return count;
	else if(n[c] < key)
		return search(n, key, c+1, l, count+1);
	else
		return search(n, key, p, c-1, count+1);
}

int main(){
	int *data, n, key;
	while(true){
		std::cin >> n;
		if(n==0)
			return 0;
		data = new int[n];
		for(int i=0; i<n; i++)
			std::cin >> data[i];
		std::cin >> key;
		std::cout << search(data, key, 0, n-1, 1) << std::endl;
		delete[] data;
	}
}

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

int box[10000];
int num = 0;
int findn;
bool check(int begin, int end){
	if (begin > end)return true;
	num++;
	if (box[(begin + end) / 2]>findn)check(begin, (begin + end) / 2-1);
	else if (box[(begin + end) / 2]<findn)check((begin + end) / 2+1, end);
	else if (box[(begin + end) / 2] == findn)return true;
	return false;
}

int main(){
	int n;
	while(1){
		num=0;
		cin >> n;
		if(n==0)break;
		for (int i = 0; i<n; i++){
			cin >> box[i];
		}
		cin >> findn;
		bool TF=check(0, n - 1);
		cout << num << endl;
	}
	return 0;
}

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

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main()
{
	int n;
	while(cin >> n && n)
	{
		vector<int> v;

		rep(i,n)
		{
			int temp;
			cin >> temp;
			v.push_back(temp);
		}

		int p;
		cin >> p;
		
		int l = 0;
		int r = n-1;
		int count = 0;

		while(true)
		{
			int mid = (l + r) / 2;

			if(l > r) break;

			count++;

			if(v[mid] == p) break;

			if(v[mid] < p)
			{
				l = mid + 1;
			}
			else
			{
				r = mid - 1;
			}
		}

		cout << count << endl;
	}
	return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, ans, a[1000], res;

int main(){
	while (cin >> n&&n){
		res = 0;
		fill(a, a + 1000, 0);
		REP(i, n)cin >> a[i];
		cin >> ans;
		int lb = -1, ub = n;
		while (ub - lb > 1){
			/*cout << ub << " " << lb << endl;*/
			int mid = (ub + lb) / 2;
			if (a[mid] < ans){
				lb = mid;
				res++;
			}
			else if (a[mid] > ans){
				ub = mid;
				res++;
			}
			else{
				res++;
				break;
			}
		}
		cout << res << endl;
	}
}