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

            if(v[mid] == p || b[mid]) break;
            else if(v[mid] > p){
                ub = mid;
            }
            else {
                lb = mid;
            }
            b[mid] = true;
        }
        cout << count << endl;
    }
}

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

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

C++: #include<iostream>
using namespace std;
int a[101];
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-1,mid;
		while(true){
			if(left>right)break;
			mid=(left+right)/2;
			if(a[mid]==key)break;
			if(a[mid]<key)left=mid+1;
			if(a[mid]>key)right=mid-1;
			ans++;
		}
		cout<<ans<<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 = 1;
    cin >> key;
    int l,r,m;
    l = 0,r = n-1;
    while(l < r){
      m = (l+r)/2;
      if(vec[m] == key)break;
      if(vec[m] > key)r = m;
      else l = m+1;
      cnt++;
    }
    cout << cnt << endl;


  }

return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef pair<int,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
	int N;
	while(scanf("%d",&N),N){
		int array[128];
		rep(i,N){
			scanf("%d",&array[i]);
		}
		int M;
		scanf("%d",&M);
		int l = 0;
		int r = N;
		int cnt = 0;
		while(l < r){
			cnt++;
			int med = (l+r-1)/2;
			if(array[med] == M)break;
			if(array[med] > M)r = med;
			else l = med+1;
		}
		printf("%d\n",cnt);
	}
    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 = 1;
		int l = 0, r = v.size() - 1;
		while( l < r )
		{
			int mid = ( l + r ) / 2;
			
			if( v[mid] < b )
				l = mid + 1;
			else if( v[mid] > b )
				r = mid - 1;

			++ans;
		}

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

	return 0;
}

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

int main()
{
	int N;
	while(cin >> N, N)
	{
		int b[100];
		for(int i=0; i<N; i++)
			cin >> b[i];
		
		int s, lo=0, hi=N-1, cnt=0;
		cin >> s;
		
		while(hi>=lo)
		{
			cnt++;
			int mi=(hi+lo)/2;
			if(b[mi]==s) break;
			
			s>b[mi]?lo=mi+1:hi=mi-1;
		}
		cout << cnt << endl;
	}
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>

#define f first
#define s second
#define mp make_pair

#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()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int main(){
  int n;
  while(cin>>n, n){
    vector<int> v(n);
    REP(i,n) cin>>v[i];
    
    int cnt = 0;
    int low = 0, high = n-1;
    int s; cin>>s;
    while(true){
      int mid = (low+high)/2;
      //cout << "mid=" << mid << endl;
      cnt++;
      if(v[mid] == s) break;
      if(low == high) break;
      if(v[mid] > s){
	high = mid-1;
      }else{
	low  = mid+1; 
      }
      if(low > high) break;
    }
    cout << cnt << endl;
  }
  return 0;
}

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


int main(){
    int n, arr[100], key;
    while(scanf("%d", &n) != EOF && n){
        for(int x = 0; x < n; x++){
            scanf("%d", &arr[x]);
        }
        scanf("%d", &key);
        int left = 0, right = n-1, mid, count = 0;
        while(left <= right){
            count++;
            mid = (left + right) / 2;
            if(arr[mid] == key) break;
            if(arr[mid] < key) left = mid + 1;
            if(arr[mid] > key) right = mid - 1;
        }
        printf("%d\n", count);
    }
    return 0;
}

C++: #include <iostream>
#include <stdlib.h>

using namespace std;

int main(int argc, char **argv)
{
	int n, *a, t, m, c, p, q;
	
	while(1){
		cin >> n;
		if(n == 0){
			break;
		}
		a = (int *)calloc(n, sizeof(int));
		
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		cin >> m;
		p = c = 0;
		q = n;
		t = (n-1+p) / 2;
		while(t != p){
			if(a[t] < m){
				p = t;
				t = (q+p) / 2;
			} else {
				q = t;
				t = (q+p) / 2;
			}
			c++;
		}
		cout << c << endl;
		
		free(a);
	}
	
	return 0;
}