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<bits/stdc++.h>
using namespace std;

int main()
{
  int n;
  while( cin >> n, n ) {
    int target;
    int cnt = 0;
    int l = 0, r = n-1, m;
    int data[100001];
   
    for(int i=0; i<n; i++) cin >> data[i];
    cin >> target;
    
   

    while( l <= r ) {
      m = (l+r) / 2;
      cnt++;
      if( data[m] == target ) break;
      if( target > data[m] ) l = m+1;
      else r = m-1;
    }

    cout << cnt << endl;
  }

}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

int main()
{
    int n;
    while(cin >> n && n)
    {
        vector<int> num;
        int t, des;
        REP(n){ cin >> t; num.push_back(t);}
        cin >> des;

        int ls = 0, rs = n - 1, ans = 1;
        while(ls < rs)
        {
            //cout << "center = " << (ls + rs) / 2 << endl;
            ans++;
            if(num[(ls + rs)/2] == des) break;

            if(num[(ls + rs)/2] < des) ls = (ls + rs) / 2 + 1;
            else rs = (ls + rs) / 2 - 1;
        }
        cout << ans << endl;
    }

    return 0;
}

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


int main(){
    int n, search;
    while (cin >> n && n){
	int inp[101];
	for (int i = 0; i < n; i++) cin >> inp[i];
	cin >> search;

	int *s = inp, *e = inp + n - 1, *p = inp + n/2;
	int ans = 0;
	int b = 0;
	for (int i = 0; i < 10; i++){
	    if (p == s && p == e) break;
	    if (*p == search) break;
	    else if (*p > search){
		e = p;
		p = s + (e - s)/2;
	    }
	    else if (*p < search){
		s = p+1;
		p = s + (e - s)/2 + 1;
	    }

	    ans++;
	}

	cout << ans << endl;
    }
}

C++: //copy #1124820 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
 
#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)

int main (void) {
    int n;
    int a[100];
    while(cin>>n && n){
        rep(i,n)cin>>a[i];
        int f;
        cin>>f;
        int l=0; int r=n-1;
        int ans=0;
        while(l<=r) {
            ans++;
            int m=(l+r)/2;
            if(a[m] == f) break;
            else if(a[m]<f)l=m+1;
            else r=m-1;
            m=(l+r)/2;
        }
        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

int a[100000];
int n;

int binary_search(int N){

  int r = n;
  int l = 0;
  int cnt = 0;
  int x = l;

  while(1){

    x = (r + l)/2;

    if( a[x] == N ){
      //cout << "match" << endl;
      cnt++;
      break;
    }
    else if( a[x] < N ){
      // cout << "right" << endl;
      cnt++;
      l = x;
    }
    else if( N < a[x] ){
      //cout << "left" << endl;
      cnt++;
      r = x;
    }
  }
  return cnt;
}

int main(void){

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

C++: #include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back


int main() {
    int n;
    while(cin>>n){
        if(n==0)break;
        
        int data[200]={};
        rep(i,n){
            cin>>data[i];
        }
        int k;
        cin>>k;
        
        int sum=0;
        
        int left=0,right=n-1;
        int cent;
        while(1){
            cent=( left+right )/2;
            sum++;
            if(data[cent]==k || left>=right )break;
            if(data[cent]>k){
                right=cent-1;
            }
            if(data[cent]<k){
                left=cent+1;
            }
        }
        cout<<sum<<endl;
    }

    return 0;
}

C++: #include <iostream>
using namespace std;
 
void bubble(int N, int data[]){
    int tmp=0;
    int cnt=0;
    int i=0, j=0;
     
    for(i=0;i<N;++i){
        cnt = 0;
        for(j=N-1;j>i;--j){
            if(data[j]<data[j-1]){
                tmp       = data[j-1];
                data[j-1] = data[j];
                data[j]   = tmp;
                cnt++;
            }
        }
        if(cnt==0) break;
    }
}
 
int BS(int key, int array[], int head, int tail, int count){
	count++;
	
    if(array[(head+tail)/2] == key){
    	return count;
    }else{
    	if(head>=tail){
    		return count;
    	}
        else if(array[(head+tail)/2] > key){
        	return BS(key, array, head, (head+tail)/2 - 1, count);
        }
        else{
        	return BS(key, array, (head+tail)/2 + 1, tail, count);
        }
    }
}
 
int main() {
    int N=0;
    int data[100];
    int key=0;
     
    while(cin >> N, N!=0){
        for(int i=0; i<N; ++i){
            cin >> data[i];
        }
        bubble(N, data);
        
        cin >> key;
         
        cout << BS(key, data, 0, N-1, 0) << endl;
         
        for(int i=0;i<N;++i){
            data[i] = 0;
        }
    }
}

C++: #include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int main()
{
	int n;
	while(scanf("%d", &n), n){
		int a[100];
		rep(i, n)
			scanf("%d", &a[i]);
		
		int key;
		scanf("%d", &key);
		
		int cnt = 0;
		int left = 0, right = n;
		while(left < right){
			++cnt;
			int mid = (left + right-1) / 2;
			if(a[mid] == key)
				break;
			if(a[mid] < key)
				left = mid + 1;
			else
				right = mid;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

C++: #include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<int> x(n);
        for(int i=0; i<n; ++i)
            cin >> x[i];
        int y;
        cin >> y;

        int ret = 0;
        int a = 0;
        int b = n-1;
        while(a <= b){
            int c = (a + b) / 2;
            ++ ret;
            if(x[c] == y)
                break;
            if(x[c] < y)
                a = c + 1;
            else
                b = c - 1;
        }

        cout << ret << endl;
    }
}