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 main()
{
  int n;
  for(;cin>>n,n;)
    {
      int data[n];
      for(int i=0;i<n;i++)
	{
	  cin>>data[i];
	}
      int s;
      cin>>s;
      int hi=0,lo=n-1;
      int cnt=0;
      while(true)
	{
	  int p = (hi+lo)/2;
	  cnt++;
	  //	  cout<<"HI:"<<hi<<" LO:"<<lo<<" "<<cnt<<endl;
	  //	  cout<<"data[p]:"<<data[p]<<" s:"<<s<<endl;
	  if(data[p]==s)
	    break;
	  if(hi>=lo)
	    break;	 
	  if(data[p]<s)
	    hi=p+1;
	  else
	    lo=p-1;
	}
      cout<<cnt<<endl;
    }
}

C++: #include<iostream>

using namespace std;



int main(){
	int num[101],r,l,c;
	int kazu, target, t;
	int i;

	while (1){
		t = 0;
		cin >> kazu;

		if (kazu == 0){
			break;
		}

		for (i = 0; i < kazu; i++){
			cin >> num[i];
		}

		cin >> target;


		l = 0;
		r = (kazu - 1);
		t = 0;
		while (1){
			c = (l + r) / 2;
			t++;
			if (num[c] == target){
				break;
			}else if (r<=l){
				break;
			}else if(num[c] < target){
				l = c + 1;
			}else{
				r = c - 1;
			}
								
		}


		cout << t << endl;
	}

}

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 1;
	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], ans, k;
	while(cin >> n){
		if(!n) break;
		ans = 0;
		for(int i = 0;i<n;i++){
			cin >> a[i];
		}
		cin >> k;
		cout << nibn(a,0,n,k) << endl;
	}
	return 0;
}

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;
    while(l < r){
      m = (l+r)/2;
      cnt++;
      if(vec[m] == key)break;
      if(vec[m] > key)r = m;
      else l = m+1;
    }
    cout << cnt << 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;
      ++ans;
      if(mid == lb){
        break;
      }
      if(v[mid] < v[n]){
        lb = mid;
      }
      else{
        ub = mid;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main(){
	int n;
	while(cin>>n,n){
		int a[100];
		for(int i=0;i<n;i++)cin>>a[i];
		int k;
		cin>>k;
		
		int ans=0;
		int si=0,li=n-1;
		while(li-si>0){
			int md=(li+si)/2;
			if(a[md]<k){
				si=md+1;
				ans++;
				}
			else if(a[md]>k){
				li=md-1;
				ans++;
				}	
			else{
				ans++;
				break;
				}	
			}
		cout<<ans<<endl;	
		}
		return 0;
	}

C++: #include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    while(cin >> n, n){
        vector<int> v(n);
        for (auto &&i : v) scanf("%d", &i);
        int x; cin >> x;
        int l = 0, r = n-1, ans = 0;
        while(l <= r){
            ans++;
            int mid = (l+r)/2;
            if(v[mid] == x) break;
            if(v[mid] > x) r = mid-1;
            else l = mid+1;
        }
        cout << ans << "\n";
    }
    return 0;
}

C++: #include <iostream>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
int main(){
	int n, a[110], t;
	while(cin >> n, n) {
		rep(i,n) {
			cin >> a[i];
		}
		cin >> t;
		int lo = 0, hi = n-1, cnt = 0, mid = -1;
		while(hi >= lo) {
			mid = (hi+lo) / 2;
			cnt++;
			if(a[mid]==t) break;
			else if(a[mid]<t) lo = mid+1;
			else hi = mid-1;
		}
		cout << cnt << endl;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin>>n,n){
  int a[n];
  for (int i=0;i<n;++i){
    cin>>a[i];
  }
  
  int goal;
  cin>>goal;
  int left,right;
  
  left=0;
  right=n;
  if(a[n/2]==goal){
    cout<<1<<endl;
    continue;
  }
  int sum=1;
  while(left<right){
    if( a[(left+right)/2]==goal )break;
    if(a[(left+right)/2]>goal){right=(left+right)/2;}
    if(a[(left+right)/2]<goal){left=(left+right)/2+1;}
    sum++;
  }
  //if(left==right){
    cout<<sum<<endl;
    //}
  
  
 }
 return 0;
}

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

int n,num[100],aid,sum;

void reading();
void binary();

int main(){
	while(1){
		sum=0;
		cin >> n;
		if(n==0)break;

		reading();
		sort();
		binary();


		cout << sum << endl;
	}
	return 0;
}

void reading(){
	for(int i=0;i<n;++i)cin >> num[i];
	cin >> aid;
}

void binary(){
	int a=0,b=n-1,c;
	while(1){
		++sum;
		c = (a+b)/2;
		if(num[c]==aid || a==b)break;
		if(num[c]>aid)b = c-1;
		else a = c+1;
	}
}