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 <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; 1 < ub - lb; ans++)
		{
			int mid = (ub + lb) / 2;
			if(v[mid] <  target) lb = mid;
			if(v[mid] >  target) ub = mid;
			if(v[mid] == target) break;
		}
		
		cout << ans << endl;
	}
}

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

int find( int* a, int b, int e, int t )
{
	if( b >= e ){
		return 1;
	}
	int m = ( b + e / 2 );
	if( t < a[ m ] ){
		return 1 + find( a, b, m - 1, t );
	}
	if( t > a[ m ] ){
		return 1 + find( a, m + 1, e, t );
	}
	return 1;
}


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 - 1, d ) << endl;
	}

	return 0;
}

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

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( a[ m ] == d || e - s < 0 ){
		return 1;
	}
	if( d > a[ m ] ){
		s = m + 1;
	}
	if( d < a[ m ] ){
		e = m - 1;
	}
	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 - 1, d ) << endl;
	}

	return 0;
}

C++: #include <iostream>
#include <math.h>
using namespace std;
int main(){
    int a, b, times;
    int i1, tyuusinn, yousosuu, yousosuu2;
    while(1){
    cin >> a;
    if(a==0){break;}
    i1=0;
        times=0;
    int w[a];
    while(1){
        cin >> b;
        w[i1]=b;
        i1++;
        if(i1==a)break;
    }
    sort(w, w+a);
    cin >> b;
    yousosuu=a;
    
    tyuusinn=(yousosuu-1)/2;
        while(1){
    times++;
    yousosuu2=(yousosuu-1)/2;
    if(w[tyuusinn]==b){break;}
    else if(w[tyuusinn]>b){
        tyuusinn=tyuusinn-yousosuu+yousosuu2/2;
        yousosuu=tyuusinn-yousosuu+yousosuu2+1;
    }
    else{
        if(yousosuu%2==0){
            tyuusinn=tyuusinn+yousosuu2/2-1;
            yousosuu=tyuusinn+yousosuu2+1;
        }
        else{
            tyuusinn=tyuusinn+(yousosuu2+1)/2+1;
            yousosuu=tyuusinn+yousosuu2;
        }
    }
            if(yousosuu==0){break;}
        }
        
    cout << times << endl;
}
    return 0;
}

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

std::vector<int> v;

int main()
{
	int n;
	while( std::cin >> n, n )
	{
		v.clear();

		for( int i = 0; i != n; ++i )
		{
			int a;
			std::cin >> a;
			v.push_back( a );
		}

		int b;
		std::cin >> b;

		int ans = 0;
		int l = 0, r = v.size() - 1;
		while( l <= r )
		{
			int mid = ( l + r ) / 2;

			++ans;

			if( r <= l )
				break;

			if( v[mid] < b )
				l = mid + 1;
			else if( v[mid] > b )
				r = mid - 1;
			else
				break;
		}

		std::cout << ans << std::endl;
	}

	return 0;
}

C++: #include <cstdio>
#define buf 1000001
using namespace std;
int cnt,b[buf]={0};
void binary_search(int d,int a);

int main(void){
  int i,j,a,n;
  char str[200];

  for( ; ; ){
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&a);
    if(a==0) break;
    for(i=0;i<a;i++){
      fgets(str,sizeof(str),stdin);
      sscanf(str,"%d",&n);
      b[i]=n;
    }
    cnt=1;
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&n);
    binary_search(n,a);
    printf("%d\n",cnt);
  }
  return 0;
}

void binary_search(int n,int a){
  int left,right,mid;
  left = 0; right = a-1;
  while(left < right){
    mid = (left + right)/2;
    if(b[mid] == n)
      break;
    else if(n < b[mid])
      right = mid;
    else if(n > b[mid])
      left = mid+1;
    cnt++;
  }
}

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

int main(){
    int n;
    while(cin >> n, n){
        vector<int> v(n);
        for(int i=0; i < n; i++) cin >> v[i];
        int k; cin >> k;
        int lb = -1, ub = n, count = 0;
        while (ub - lb > 1) {
            int mid = (lb + ub) / 2;
            count++;
            if(v[mid] == k) break;
            if (v[mid] >= k) {
                ub = mid;
            } else {
                lb = mid;
            }
        }
        cout << count << endl;
    }
}

C++: #define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

int main(){
	int n;
	while(~scanf("%d",&n)){
		if(n==0) break;

		int* a = new int[n];
		for(int i=0;i<n;i++){
			scanf("%d",a+i);
		}

		int dst;
		scanf("%d",&dst);
		
		int lb = 0;
		int ub = n-1;

		int res=0;
		for(int i=0;i<50;i++){
			res++;
			int md = (lb+ub)/2;

			if(dst == a[md]){
				break;
			}
			else if(dst < a[md]){
				ub = md-1;
			}
			else{
				lb = md+1;
			}
			
			if(ub<lb){
				break;
			}
		}
		printf("%d\n",res);
		delete[] a;
	}
}