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 bin_search(int x[],int size,int key)
{
	int low = 0,high = size-1;
	int count=0;
	while(low <= high){
		count++;
		int mid = (low+high)/2;
		if(x[mid] == key)
			return count;
		else if(x[mid] > key)
			high = mid-1;
		else
			low = mid+1;
	}
	return count;
}
int main()
{
	int size;
	int key;
	int x[101];
	while(cin >> size){
		if(size == 0)
			break;
		for(int i=0;i<size;i++){
			cin >> x[i];
		}
		cin >> key;
		cout << bin_search(x,size,key) << endl;
	}
	return 0;
}

/*
#include <iostream>
using namespace std;

static int count = 0;

int binary_search(int data[], int n, int x)
{
	int low = 0;
	int high = n-1;
	while(low<=high){
		count++;
		int middle = (high+low)/2;
		if(x==data[middle])
			return middle;
		else if(x<data[middle])
			high = middle-1;
		else
			low = middle+1;
	}
	return -1;
}

int main()
{
	const int n = 100000;
	int data[n];
	for(int i=0;i<n;i++){data[i] = i;}

	for(int i=0;i<n;i++){
		binary_search(data, n, data[i]);
	}

	cout << static_cast<double>(count)/n << endl;
	return 0;
}
*/

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 find( int* a, int b, int e, int t )
{
	int m = ( b + e ) / 2;
	if( m == b || m == e || b > e ){
		return 1;
	}
	if( t < a[ m ] ){
		return 1 + find( a, b, m - 1, t );
	}
	if( t > a[ m ] ){
		return 1 + find( a, m + 1, e, t );
	}
	return 1;
}


int main()
{
	int n;
	while( cin >> n && n ){
		int a[ 100 ] = {0};
		for( int i = 0; i < n; ++i ){
			cin >> a[ i ];
		}
		int d;
		cin >> d;
		cout << find( a, 0, n - 1, d ) << endl;
	}

	return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int n;
	while (cin >> n, n) {
		int a[110]; int k;
		for (int i = 0; i < n; i++)cin >> a[i]; cin >> k;
		int l = 0, r = n - 1;
		int cnt = 0;
		while (l <= r) {
			cnt++;
			int m = (l + r) / 2;
			if (a[m] == k) { cout << cnt << endl; goto heaven; }
			else if (a[m] < k)l = m + 1;
			else if (a[m] > k)r = m - 1;
		}
		cout << cnt << endl;
	heaven:;
	}
}

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) {
            if (r + 1 == l || r == l) {
                count++;
                break;
            }
            mid = (r+l) / 2;
            count++;
            if (a[mid] == f) {
                break;
            } else if (a[mid] < f) {
                r = mid+1;
            } else if (a[mid] > f) {
                l = mid-1;
            }
        }
        cout << count << endl;
    }
    return 0;
}

C++: 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,k;
  while(1){
    cin>>n;
    if(n==0)break;
    vi a(n);
    rep(i,n)cin>>a[i];
    cin>>k;
    int r=n-1;
    int l=0;
    rep(i,n){
      int mid=(r+l)/2;
      if(r<=l||a[mid]==k){
	cout<<i+1<<endl;
	break;
      }
      if(a[mid]<k)l=mid+1;
      else r=mid-1;
    }

  }
}

C++: #include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define vi vector<int>
#define VS vector<string>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back

using namespace std;

int main(){
    int n;
    bool b[110];
    while(cin >> n, n){
        fill(b, b+110, false);
        vi v;
        for(int i=0; i < n; i++){
            int p;
            cin >> p;
            v.pb(p);
        }
        int p;
        cin >> p;

        int count = 0;
        int lb = 0, ub = n;
        while(true){
            int mid = (lb + ub) / 2;
            if((lb + ub) % 2 == 1) mid--;

            if(v[mid] == p || b[mid]) break;
            else if(v[mid] > p){
                ub = mid;
            }
            else {
                lb = mid;
            }
            b[mid] = true;
            count++;
        }
        cout << count << endl;
    }
}

C++: #include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main() {
	int n, x;
	while (1) {
		cin >> n;
		if (n == 0) break;
		vi d(n);
		rep(i, 0, n) {
			cin >> d[i];
		}
		cin >> x;
		int cnt = 0, l = 0, r = n - 1;
		while (1) {
			int mid = (l + r) / 2;
			cnt++;
			if (l >= r) break;
			if (d[mid] > x) {
				r = mid - 1;
			}
			else if (d[mid] < x) {
				l = mid + 1;
			}
			else if (d[mid] == x) {
				break;
			}
		}
		cout << cnt << endl;
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        int num[n],ans;
        for(int i=0;i<n;i++)cin>>num[i];
        cin>>ans;
        int serch,kawa[2]={0,n-1};
        for(int i=1;;i++){
            serch=(kawa[0]+kawa[1])/2;
            if(num[serch]==ans||kawa[0]==kawa[1]||n/2+n%2==i){
                cout<<i<<endl;
                break;
            }
            if(num[serch]>ans)kawa[1]=serch-1;
            else kawa[0]=serch+1;
        }
    }
}

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

int find( int* a, int b, int e, int t )
{
	if( b >= e ){
		return 1;
	}
	int m = ( b + e ) / 2;
	if( t < a[ m ] ){
		return 1 + find( a, b, m - 1, t );
	}
	if( t > a[ m ] ){
		return 1 + find( a, m + 1, e, t );
	}
	return 1;
}


int main()
{
	int n;
	while( cin >> n && n ){
		int a[ 100 ] = {0};
		for( int i = 0; i < n; ++i ){
			cin >> a[ i ];
		}
		int d;
		cin >> d;
		cout << find( a, 0, n - 1, d ) << endl;
	}

	return 0;
}