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

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, d ) << 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=1;
		int left=0,right=n,mid;
		while(true){
			if(left>=right-(right+left)%2)break;
			mid=(left+right)/2;
			if(a[mid]==key)break;
			if(a[mid]<key)left=mid;
			if(a[mid]>key)right=mid;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int n,t[100],a,L,R,M,ans;
int main(){
  while(cin>>n&&n){
    for(int i=0;i<n;i++){
      cin>>t[i];
    }
    cin>>a;

    L=0;
    R=n-1;
    ans=0;
    while(L<=R){
      M=(L+R)/2;
      ans++;
      //cout<<t[M]<<endl;
      if(t[M]==a){
	break;
      }else if(t[M]>a){
	R=M-1;
      }else{
	L=M+1;
      }
    }
    cout<<ans<<endl;
  }
  
  return 0;
}

C++: #include <stdio.h>

int main(void)
{
	int n;
	int i;
	int a[128], key;
	int left, right, center;
	int count;
	
	while (scanf("%d", &n) && n){
		for (i = 0; i < n; i++){
			scanf("%d", &a[i]);
		}
		scanf("%d", &key); //探す数
		
		left = 0;
		right = n - 1;
		count = 0;
		while (left <= right){
			center = (left + right) / 2;
			
			count++;
			if (a[center] == key){
				break;
			}
			else if (a[center] > key){
				right = center - 1;
			}
			else {
				left = center + 1;
			}
		}
		printf("%d\n", count);
	}
	
	return (0);
}

C++: #include<iostream>
using namespace std;
int main(){
  while(true){
    int q;
    int n;
    bool found=false;
    int cmp = 0;
    cin >> n;
    int a[n];
    if( n == 0 ) break;
    for(int i = 0; i < n; ++i){
      cin >> a[i];      
    }
    cin >> q;
    int l = 0;
    int r = n-1;
    int prem=-1;
    while(l<=r){
      int m = (l+r)/2;
      //      if(prem==m)break;
      if(a[m]>q){
	++cmp;
	r=m-1;
      }else if(a[m]==q){
	++cmp;
	found=true;
	break;
      }else{
	++cmp;
	l=m+1;
      }
      prem=m;
    }
    //if(!found)++cmp;
    cout << cmp << endl;
  }
  return 0;
}

C++: #include<iostream>
using namespace std;
int a[114514];
int n, key;
int binary_search(int sum, int l, int r) {
	if (l > r)return sum;
	int m = (l + r) / 2;
	sum++;
	if (a[m] == key)return sum;
	else if (l == r&&a[m] != key)return sum;
	else if (a[m] > key)return binary_search(sum, 0, m - 1);
	else return binary_search(sum, m + 1, r);
}
int main() {
	while (cin >> n) {
		if (!n)return 0;
		for (int i = 0; i < n; i++)cin >> a[i];
		cin >> key;
		cout << binary_search(0, 0, n - 1) << endl;
	}
}

C++: #define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 29;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;
const int CLK = CLOCKS_PER_SEC;

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

int nums[100];

int main(){
	int n, p;
	while(cin >> n && n){
		rep(i, n){
			cin >> nums[i];
		}
		cin >> p;
		int l = 0, r = n - 1;
		int res = 0;
		while(r - l >= 0){
			res++;
			int mb = (l + r) / 2;
			if(nums[mb]==p) break;
			else if(nums[mb] > p) r = mb - 1;
			else l = mb + 1;
		}
		cout << res  << endl;
	}
	return 0;
}

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

int binSearch( int*, int, int, int, int );

int main(){
	int n;	// number
	int s;	// search
	int data[100];
	while(1){
		cin >> n;
		if( n == 0 ) break;

		for( int i=0; i<n; i++ ){
			cin >> data[i];
		}
		cin >> s;

		cout << binSearch( data, s, 0, n-1, 0 ) << endl;
	}
	return 0;
}

int binSearch( int *data, int s, int first, int last, int comp ){
	comp++;
	if( first >= last ){
		return comp;
	}
	int p = (first+last)/2;
	if( data[p] < s ){
		return binSearch( data, s, p+1, last, comp );
	}else if( data[p] > s ){
		return binSearch( data, s, first, p-1, comp );
	}else{
		return comp;
	}
}

C++: #include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;


int N, M;
int solve(vector<int> &v){
  int l = -1, r = (int)(v.size()), res = 0;
  while(r - l > 1){
    ++res;
    int m = (r + l) / 2;
    if(v[m] == M) break;
    else if(v[m] > M) r = m;
    else l = m;
  }
  return res;
}

int main() {
  while(cin >>N && N){
    vector<int> v(N);
    REP(i, N) cin >>v[i];
    cin >>M;
    cout <<solve(v) <<endl;
  }
  return 0;
}

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=n/2,kawa[2]={0,n};
        for(int i=1;;i++){
            if(num[serch]==ans||i==n-1){
                cout<<i<<endl;
                break;
            }
            else if(num[serch]>ans){
                    kawa[1]=serch;
                    serch=(kawa[0]+kawa[1])/2;
            }
            else {
                    kawa[0]=serch+1;
                    serch=(kawa[0]+kawa[1])/2;
            }
        }
    }
}

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

int main(){
	int n;
	while( cin >> n, n ){
		int a[101], key;
		for(int i=0 ; i < n ; i++ ){
			cin >> a[i];
		}
		cin >> key;
		
		int low = 0, high = n, mid, cnt = 0;
		while( low < high ){
			cnt++;
			mid = (low + high) / 2;
			
			if( a[mid] == key ){
				break;
			}else if( a[mid] < key ){
				if( low == mid ) break;
				low = mid;
			}else{
				if( high == mid ) break;
				high = mid;
			}
		}
		cout << cnt << endl;
	}
}