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>
#include <vector>

using namespace std;

int main(){
    while(true) {
        int n = 0;
        cin >> n;
        if(n == 0) break;
        vector<int> v(n);
        int x;
        for(int i = 0; i < n; ++i){
            cin >> v[i];
        }
        cin >> x;
        int left = 0;
        int right = n - 1;
        int cnt = 0;
        while(true){
            int pivot = (right + left) / 2;
            int elem = v[pivot];
            if(left > right) break;
            cnt++;
            if( elem < x ){
                left = pivot + 1;
            } else if ( elem > x ) {
                right = pivot - 1;
            } else {
                break;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

int n,a[100],t;

int main(){
	while(cin>>n&&n){
		rep(i,n)cin>>a[i];
		cin>>t;
		int lb=0,ub=n-1;
		int ans=0;
		while(++ans){
			//cout<<ans<<" "<<a[lb]<<" "<<a[ub]<<" "<<a[(lb+ub)/2]<<endl;
			if(a[(lb+ub)/2]==t||lb==ub||lb>ub){cout<<ans<<endl;break;}
			else if(a[(lb+ub)/2]<t)lb=(lb+ub)/2+1;
			else ub=(lb+ub)/2-1;
			if(lb>ub){cout<<ans<<endl;break;}
		}
	}
}

C++: #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stdexcept>
#include<cmath>
#include<memory>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<deque>
#include<sstream>
#include<iomanip>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<map>
#include<set>
#include<list>
#include<cassert>
#include<deque>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<27
#define all(n) n.begin(),n.end()
#define insert(a,b,c,d) PP(P(a,b),P(c,d))
#define F first
#define S second
#define pb push_back
#define pf push_front
#define LIM 100000
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef long long ll;
typedef unsigned long long ull;

int main(){

  while(true){
    int n;
    cin >> n;
    if(n == 0)break;
    vector<int> vec;
    rep(i,n){
      int in; cin >> in;
      vec.pb(in);
    }
    int key,cnt = 0;
    cin >> key;
    int l,r,m;
    l = 0,r = n-1;
    while(l <= r){
      m = (l+r)/2;
      cnt++;
      if(vec[m] == key)break;
      if(vec[m] > key)r = m-1;
      else l = m+1;
    }
    cout << cnt << endl;


  }

return 0;
}

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

int T[100010];
int find(int m,int x){
	int r=0,l=m-1,ans=0;
	while(1){	
		if(r>l)break;
		ans++;
		if(T[(r+l)/2]==x)return ans;
		if(T[(r+l)/2]>x)l=(r+l)/2-1;
		else if(T[(r+l)/2]<x)r=(r+l)/2+1;
	}
	return ans;
}
int main(){
	int n,k,num,ans;
	while(1){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>T[i];
		}
		cin>>k;
		ans=find(n,k);
		cout<<ans<<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;i<n;i++){
        int center=(low+high)/2;
        if(a[center]==X){
            cnt=i+1;
            break;
        }
        else if(a[center]<X) low=center+1;
        else high=center-1;
    }
    cout << cnt << endl;
    }
}

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

int main() {
	int n, a[100], f, l, r, ans, piv;
	while(1) {
		cin >> n;
		if(!n) break;
		for(int i=0; i<n; ++i) cin >> a[i];
		cin >> f;
		l = 0; r = n-1; ans = 0;
		while(l<=r) {
			piv = (l+r)/2;
			ans++;
			if(a[piv]==f) {
				break;
			}
			if(a[piv]<f) {
				l = piv+1;
			}else {
				r = piv-1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

C++: #include<iostream>

int main(){
	int n, a[100], search_i;
	while(std::cin >> n, n){
		for(int i=0;i<n;i++){
			std::cin >> a[i];
		}
		std::cin >> search_i;

		int ub = n, lb = -1, t = 0;
		while(ub - lb > 1){
			int mid = (ub + lb) / 2;
			if(a[mid] >= search_i){
				ub = mid;
			}else{
				lb = mid;
			}
			t++;
		}

		std::cout << t << std::endl;
	}
}

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

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <string>
#include <cmath>
#include <map> 
using namespace std;
 
const int MAX= 10000100;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()

int main(void){
  int n ;
  while(cin>>n,n){
    int cnt = 0;
    vector<int> vec(n);
    for(int i = 0 ; i < n ; i ++){
      cin>>vec[i];
    }
    int find;
    cin>>find;
    bool ans = false;
    int l = 0 , r = n-1;
    while(l<=r){
      int mid = (l + r)/2;
      if(vec[mid]<find){
        l = mid + 1; 
      }else if(vec[mid]>find){
        r = mid - 1;
      }else{
        ans = true;
        cnt++;
        break;
      }
      cnt++;
    }
    cout<<cnt<<endl;
  }
  
}

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(true) {
	        times++;
		mid = (right + left) / 2;
		if((right - left) == 0){
			break;
		}
		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 <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

int n,a[100],t;

int main(){
	while(cin>>n&&n){
		rep(i,n)cin>>a[i];
		cin>>t;
		int lb=0,ub=n-1;
		int ans=0;
		while(++ans){
			//cout<<ans<<" "<<lb<<" "<<ub<<" "<<a[(lb+ub)/2]<<endl;
			if(a[(lb+ub)/2]==t||lb==ub||lb>ub){cout<<ans<<endl;break;}
			else if(a[(lb+ub)/2]<t)lb=(lb+ub)/2+1;
			else ub=(lb+ub)/2-1;
		}
	}
}