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>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

	int n;
	while(cin>>n&&n!=0){
		vector<int> nums;
		int t;
		for(int i = 0; i < n; i++){
			cin>>t;
			nums.push_back(t);
		}
		int s;
		cin>>s;
		int ub=n;
		int lb=-1;
		int cnt=0;
		while(1){
			int mid=ub+lb;
			mid/=2;
			cnt++;
			if(nums[mid]==s||ub==lb){
				break;
			}
			else if(nums[mid]>s){
				ub=mid-1;
			}
			else if(nums[mid]<s){
				lb=mid+1;
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}

C++: #include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i;
  int a[100],p,n,c,mn,mx;
  for(;;){
    cin>>n;
    if(n==0)
      break;
    for(i=0;i<n;i++)
      cin>>a[i];
    cin>>p;
    mn=0;
    mx=n-1;
    for(c=1;;c++){
      if(a[(mn+mx)/2]==p)
	break;
      else if(a[(mn+mx)/2]>p){
	if(mn==mx)
	  break;
	mx=(mn+mx)/2-1;
      }else{
	if(mn==mx)
	  break;
	mn=(mn+mx)/2+1;
      }
    }
    cout<<c<<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
#include <cmath>
#include <cstdio>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()

using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int num[101];
int main(void){
	int n;
	while(cin >> n, n){
		rep(i, n) cin >> num[i];
		int x;
		cin >> x;

		int lb = 0, ub = n-1;
		int ans = 0;
		while(ub >= lb){
			int mid = (ub+lb)/2;
			ans++;
			if(num[mid] == x) break;
			if(num[mid] < x) lb = mid+1;
			else ub = mid-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 (l <= r){
			center = (l + r) / 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 <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define INF 1000000001
#define MOD 10000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const ull B=100000007;
int main(){
      int n;
      while(cin>>n&&n){
            int lb=-1,ub=n,a[n],cnt=0,k;
            REP(i,n)cin>>a[i];
            cin>>k;
            while(ub-lb>1){
                  int mid=(lb+ub)/2;
                  cnt++;
                  if(k==a[mid])break;
                  if(a[mid]>k)ub=mid;
                  else lb=mid;
            }
            cout<<cnt<<endl;
      }
}

C++: #include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	for (int n; cin >> n&&n;) {
		vector<int> a(n);
		rep(i, 0, n)cin >> a[i];
		int s; cin >> s;
		int l = 0, r = n - 1;
		int cnt = 0;
		while (true) {
			if (r - l < 0)break;
			cnt++;
			if (r - l == 0)break;
			int m = (l + r) / 2;
			//dump(m); dump(l); dump(r);
			if (a[m] > s)r = m - 1;
			else if (a[m] < s)l = m + 1;
			else break;
		}
		cout << cnt << 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 <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pll> pip;
const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS  = 1e-9;

int n;
int a[112345];

int main() {
	while (cin >> n, n) {
		REP(i, n) scanf("%d", a + i);
		
		int k; cin >> k;
		
		int l = 0, r = n - 1;
		int c = 0;
		while (r - l >= 0) {
			int m = (l + r) / 2;
			c++;
			
			if (r == l) break;
			
			if (a[m] < k) l = m + 1;
			else r = m - 1;
		}
		
		cout << c << 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 >= 0){
		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;
}

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;
    }
}