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 <stdio.h>
int n, a[100], t;
int main() {
	while(true) {
		scanf("%d", &n);
		if(n == 0) break;
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		scanf("%d", &t);
		int c = 1;
		int l = 0;
		int r = n - 1;
		while(r - l > 0) {
			int m = (l + r) / 2;
			if(a[m] == t) break; c++;
			if(a[m] < t) {
				l = m + 1;
			}
			else {
				r = m - 1;
			}
		}
		printf("%d\n", c);
	}
	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 = 0;
    left = 0;
    right = n-1;
    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;
	break;
      }
    }
    cout<<count<<endl;
  }

  return 0;
}

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

int nibn(int a[], int s, int e, int k);
int nibn(int a[], int s, int e, int k){
	if(s>e) return 0;
	if(a[(s+e)/2] == k){
		return 1;
	}
	else if(a[(s+e)/2] < k){
		return 1 + nibn(a,(s+e)/2+1,e,k);
	}
	else if(a[(s+e)/2] > k){
		return 1 + nibn(a,s,(s+e)/2-1,k);
	}
}


int main(){
	int n, a[150], k;
	while(cin >> n){
		if(!n) break;
		for(int i = 0;i<n;i++){
			cin >> a[i];
		}
		cin >> k;
		cout << nibn(a,0,n-1,k) << endl;
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int main(){
    int n,a[100],X;
    while(1){
    cin >> n;
    if(n==0)break;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    cin >> X;
    int high=n-1,low=0,cnt;
    for(int i=0;high>=low;i++){
        int center=(low+high)/2;
        if(a[center]==X){
            cnt=i;
            break;
        }
        else if(a[center]<X) low=center+1;
        else high=center-1;
    }
    cout << cnt+1 << endl;
    }
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n;
	while(cin >> n , n){
		int need , ans = 0;
		vector<int> d(n);
		rep(i,n) cin >> d[i];
		
		cin >> need;
		int l = 0 , r = n-1;
		while( l < r ){
			ans++;
			int m = (l+r)/2;
			if(d[m] > need) r = m-1;
			else if(d[m] < need) l = m+1;
			else break;
		}
		cout << ans+1 << endl;
	}
}

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

using namespace std;

const int MAX = 101;
int data[MAX];
int n;
int ans;
int wanted;

void solve(){
  int start = 0;
  int end = n;
  //sort(data,data+n);
  while(1){
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start > end) break;
    if(data[now] > wanted) end = now-1;
    else start=now+1;
  }
}

int main(){
  while(cin >> n && n){
    ans = 0;
    for(int i = 0; i < n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  return 0;
}

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

int a[1000],n,cnt,L,R,M,p;

int main(){
	while(true){
		cin>>n;
		if(n==0){break;}
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		cin>>p;
		L=0;R=n-1;cnt=0;
		while(R>=L){
			cnt++;
			M=(R+L)/2;
			if(p==a[M]){break;}
			if(p>a[M]){L=M+1;}
			if(p<a[M]){R=M-1;}
		}
		cout<<cnt<<endl;
	}
}

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 = (l+r) / 2;
    int data[100001];
   
    for(int i=0; i<n; i++) cin >> data[i];
    cin >> target;
    
   

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

    cout << cnt << endl;
  }

}

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

#define DEBUG(x) cerr << #x << " = " << x << endl

int main() {
    for(int n; cin >> n, n; ) {
        vector<int> data(n);
        for(int i = 0; i < n; i++) cin >> data[i];
        int target; cin >> target;

        int lb = 0, ub = n - 1, mid;
        int ans = 0;
        while(++ans, mid = (ub + lb) / 2, data[mid] != target && ub > lb) {
            if(target < data[mid]) {
                ub = mid - 1;
            }
            else {
                lb = mid + 1;
            }

            if(ans > 5) break;
        }
        cout << ans << endl;
    }
}

C++: #include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i;
  int a[100],n,p;
  int mn,mx;
  while(cin>>n&&n){
    for(i=0;i<n;i++)
      cin>>a[i];
    cin>>p;
    mn=0;
    mx=n-1;
    for(i=1;;i++){
      if(0){
      }else if(a[(mn+mx)/2]==p){
	break;
      }else if(a[(mn+mx)/2]<p){
	if(mn==mx)
	  break;
	mn=(mn+mx)/2+1;
      }else if(a[(mn+mx)/2]>p){
	if(mn==mx||mn==(mn+mx)/2)
	  break;
	mx=(mn+mx)/2-1;
      }
    }
    cout<<i<<endl;
  }
  return 0;
}

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

using namespace std;

const int MAX = 101;
int data[MAX];
int n;
int ans;
int wanted;

void solve(){
  int start = 0;
  int end = n-1;
  //sort(data,data+n);
  while(1){
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start >= end) break;
    if(data[now] > wanted) end = now;
    else start=now+1;
  }
}

int main(){
  while(cin >> n && n){
    ans = 0;
    for(int i = 0; i < n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  return 0;
}

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 = 1;
		while(l+1 != r){
			int med = (l+r)/2;
		//	printf("%d ",array[med]);
			if(array[med] == M)break;
			if(array[med] > M)r = med;
			else l = med;
			cnt++;
		}
		//puts("");
		printf("%d\n",cnt);
	}
    return 0;
}

C++: #include <stdio.h>

int main(void)
{
	int n;
	int x[100];
	int i;
	int max, min;
	int obj;
	int ans;
	
	while (scanf("%d", &n) && n){
		
		for (i = 0; i < n; i++){
			scanf("%d", &x[i]);
		}
		
		scanf("%d", &obj);
		
		max = n - 1;
		min = 0;
		ans = 1;
		while (1){
			
			i = (max + min) / 2;
			if (x[i] < obj){
				min = i + 1;
			}else if (x[i] > obj){
				max = i - 1;
			}else{
				break;
			}
			
			if (max == min){
				ans++;
				break;
			}
			ans++;
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}