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++: // 2011/02/05 Tazoe

#include <iostream>
using namespace std;

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

		int dat[100];
		for(int i=0; i<n; i++)
			cin >> dat[i];

		int key;
		cin >> key;

		int cnt = 0;
		for(int lef=0, rig=n-1; lef<=rig;){
			int mid = (lef+rig)/2;
			cnt++;
			if(key==dat[mid])
				break;
			else if(key<dat[mid])
				rig = mid-1;
			else
				lef = mid+1;
		}

		cout << cnt << endl;
	}

	return 0;
}

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

using namespace std;

int main(){

	int n;

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

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

		int want ;
		cin >> want ;

		int t,l,c,count ;
		t = 0 ;
		l = n - 1 ;

		for( count = 0; t <= l; count++){
			c = (t + l)/2 ;
			cout << t << " " << c << " " << l << endl;
			if( want > num[c] ){
				t = c + 1;
			} else if( want < num[c]){
				l = c - 1 ;
			} else {
				count++;
				break ;
			}
		}

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

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

int main()
{
    int n,m;
    while(cin >> n && n) {
        vector<int> v(n);
        for(int i = 0; i < n; i++) 
            cin >> v[i];

        cin >> m;
        sort(v.begin(), v.end());

        int lb, ub, cnt;
        lb = 0; ub = v.size() - 1;
        cnt = 0;
        while(lb <= ub) {
            int mb = (lb + ub) / 2;
            cnt++;
            if(v[mb] < m) {
                lb = mb + 1;
            } else if(v[mb] == m) {
                break;
            } else {
                ub = mb - 1;
            }
        }
        cout << cnt << endl;
    }
}

C++: #include<iostream>
using namespace std;
int main(){
	int n,m,d[100],hi,lo,c,md;
	while(cin>>n,n){
		hi=n-1,lo=c=0;
		for(int i=0;i<n;i++)cin>>d[i];
		cin>>m;
		while(hi>=lo){
			c++;
			md=(hi+lo)/2;
			if(d[md]<m)lo=md+1;
			else if(d[md]>m)hi=md-1;
			else break;
		}
		cout<<c<<endl;
	}
	return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
    for(int n; cin >> n; )
	{
		int target, ans = 1;
		vint v(n);
		
		rep(i, n) cin >> v[i];
		
		cin >> target;
		
		for(int lb = 0, ub = n; lb <= ub; ans++)
		{
			int mid = (ub + lb) / 2;
			if(v[mid] <  target) lb = mid + 1;
			if(v[mid] >  target) ub = mid - 1;
			if(v[mid] == target) break;
		}
		
		cout << ans << endl;
	}
}

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,cnt = 0;
		while(1){
			cnt++;
			if(up - low == 0) break;
			int mid = (up + low) / 2;
			if(a[mid] == k) break;
			if(a[mid] < k) low = mid + 1;
			else up = mid;
		}
		cout << cnt << endl;
	}
	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>
#include <algorithm>
#include <vector>
using namespace std;

int a[110];
int n, k;

//a[0], a[1], a[2]. ... , a[n - 1]?????????x?????????????????????????????????
int binary_search(int x){
    int res = 0;
	int l = 0, r = n - 1;
	//[l, r)???????????????????????????????????§??°?????????
	while(r - l >= 1){
		int m = (l + r) / 2;
        res++;
		if(a[m] == x) return res; //x??????????????£?????´???
		else if(a[m] > x) r = m - 1;
		else if(a[m] < x) l = m + 1;
	}
	//x???????????????????????£?????´???
	return res + 1;
}

int main(){
    while(cin >> n, n){
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        cin >> k;
        sort(a, a + n);
        cout << binary_search(k) << endl;
    }
}

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