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;
	while(cin >> n,n){
		int a[100],k;
		for(int i = 0;i < n;i++) cin >> a[i];
		cin >> k;
		int low = 0,up = n - 1,cnt = 0;
		while(1){
			cnt++;
			if(up <= low) break;
			int mid = (up + low) / 2;
			if(a[mid] == k) break;
			if(a[mid] < k) low = mid + 1;
			else up = mid - 1;
		}
		cout << cnt << endl;
	}
	return 0;
}

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-1;
        while(true){
            count++;
            int mid = (lb + ub) / 2;

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

C++: #include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int n;
  while (cin >> n, n) {
    int a[110];
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int k;
    cin >> k;
    int l = 0, r = n - 1, ans = 0;
    while (l <= r) {
      ans++;
      int m = (l + r) / 2;
      if (k < a[m]) r = m - 1;
      else if (a[m] < k) l = m + 1;
      else break;
    }
    cout << ans << endl;
  }

  return 0;
}

C++: #include<iostream>
using namespace std;
int a[100];
int main(){
	int n,key;
	while(true){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++)cin>>a[i];
		cin>>key;
		int ans=0;
		int left=0,right=n-1,mid;
		while(true){
			if(left>right)break;
			mid=(left+right)/2;
			ans++;
			if(a[mid]==key)break;
			if(a[mid]<key)left=mid+1;
			if(a[mid]>key)right=mid-1;
		}
		cout<<ans<<endl;
	}
	return 0;
}

C++: import math

def f(check, n, L, count):
    count += 1
    median = int(math.floor(float(n-1)/2))
    if len(L) == 1:
        return count
    elif L[median] == check:
        return count
    elif L[median] < check:
        L = L[median+1:]
    elif check < L[median]:
        L = L[:median]
    n = len(L)
    return f(check, n, L, count)

while True:
    n = int(raw_input())
    if n == 0: break
    L = [int(raw_input()) for i in range(n)]
    check = int(raw_input())
    print f(check, n, L, 0)

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

int binarySearch( int l, int r, int k, int* a )
{
    int cnt = 0;
    while( l <= r )
    {
        cnt++;
        int mid = ( l + r ) / 2;
        if( k < a[mid] )
            r = mid - 1;
        else if( k > a[mid] )
            l = mid + 1;
        else
            return cnt;
    }
    return cnt;
}

int main()
{
    int n, a[100], key;

    while( cin >> n )
    {
        if( n == 0 )
            break;

        for( int i = 0; i < 100; i++ )
            a[i] = 0;

        for( int i = 0; i < n; i++ )
            cin >> a[i];
        
        cin >> key;

        int left = 0, right = n - 1;
        cout << binarySearch( left, right, key, a ) << endl;
    }
    return 0;
}

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

using namespace std;

int main(){

	int n;
	while(cin>>n&&n!=0){
		vector<int> nums;
		int t;
		for(int i = 0; i < n; i++){
			cin>>t;
			nums.push_back(t);
		}
		int s;
		cin>>s;
		int ub=n;
		int lb=-1;
		int cnt=0;
		while(1){
			int mid=ub+lb;
			mid/=2;
			cnt++;
			if(nums[mid]==s||ub==lb){
				break;
			}
			else if(nums[mid]>s){
				ub=mid-1;
			}
			else if(nums[mid]<s){
				lb=mid+1;
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>

using namespace std;


int main(){

	int n;
	while(1){
		cin>>n;if(n==0)break;
		int P[105]={};
		for(int i=0;i<n;i++){
			cin>>P[i];}

		sort(P,P+n);
		int C=0;
		int x;
		cin>>x;
		int H=(n-1)/2;
		int L=n,S=0;
		while(S<L){
			//cout<<L<<" "<<S<<endl;
			if (L==S){
				//cout<<"%";
				C++;break;
			}
			if (P[H]==x){C++;break;}

			if(P[H]<x){S=H+1;
			H=(S+L-1)/2;C++;//cout<<"#";//cout<<H<<endl;//break;
			}
			else if(P[H]>x){L=H;
				H=(S+L-1)/2;C++;//cout<<"$";//cout<<H;//break;
			}
			
		}
		cout<<C<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define INF 1<<30

int main() {
  int n;
  while(cin >> n, n) {
    vector<int> v(n);
    REP(i,n)
      cin >> v[i];
    int a;
    cin >> a;

    sort(ALL(v));
    int lb = 0, ub = n - 1;
    int res = 0;
    while(ub-lb>=0) { // ツつアツつアツづ債適ツ督鳴づ可。
      int mid = (lb+ub)/2;
      //cout << mid << endl;
      ++res;
      if (v[mid] < a) lb = mid + 1; 
      else if (v[mid] > a) ub = mid - 1;
      else break;
    }
    // if (v[lb] != a)
    //   ++res;
    cout << res << endl;
  }
}

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

int search2(int,int,int,int[],int);

int main() {
	// your code goes here
	int n,low,high,mid,number,ans;
	int num[110]={};
	for(;;){
	cin>>n;
	if(n==0){
		break;
	}
	for(int i=0;i<110;i++){
		num[i]=0;
	}
	for(int i=0;i<n;i++){
		cin>>num[i];
	}
	cin>>number;
	sort(num,num+n);
	for(int i=0;i<n;i++){
		cout<<num[i]<<" ";
	}
	cout<<endl;
	int ans=0;
	ans = search2(0,n,number,num,ans);
	cout<<ans<<endl;
	}
	return 0;
}

int search2(int low,int high,int number,int num[],int ans){
	ans++;
	int mid=(low+high)/2;
	if(num[mid]==number||low==(high)){
		return ans;
	}else if(num[mid]<number){
		low=mid+1;
		search2(low,high,number,num,ans);
	}else if(num[mid]>number){
		high=mid;
		search2(low,high,number,num,ans);
	}
	
	
}

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)
			{
				l = mid + 1;
			}
			else
			{
				r = mid - 1;
			}
		}

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