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

C++: #include<stdio.h>

int main(void)
{
	int x[100]={0};
	int st,fn,a,n,i,ty,kai;
	while(0==0){
		scanf("%d",&n);
		if(n==0)break;		
		kai=1;  st=0; fn=n-1;
		for(i=0;i<n;i++) scanf("%d",&x[i]);
		scanf("%d",&a);
		while(0==0){
			ty=(st+fn)/2;
			if(a==x[ty]||st==fn)break;
			else if(a>x[ty])  st=ty+1;
			else fn= ty-1;
			kai++;
		}
		printf("%d\n",kai);
	}
	return 0;
}

C++: #include <iostream>

using namespace std;

#define MAX_N 101

int a[MAX_N];

int main() {
    int n, f;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> f;
        int count = 0;
        int r = 0, l = n-1;
        int mid;
        while (true) {
            mid = (r+l) / 2;
            count++;
            if (mid == r) {
                count++;
                break;
            }
            if (a[mid] == f) {
                break;
            } else if (a[mid] < f) {
                r = mid+1;
            } else if (a[mid] > f) {
                l = mid-1;
            } 
        }
        cout << count << endl;
    }
    return 0;
}

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

typedef long long ll;
int n, ans;

int binary_search(ll k, ll a[]) {
	int l = 0, r = n - 1;
	while (r - l >= 0) {
		ans++;
		int mid = (l + r) / 2;
		if (k == a[mid]) return ans;
		else if (k < a[mid]) r = mid - 1;
		else l = mid + 1;
	}
	return ans;
}
int main() {
	while (cin >> n && n) {
		ans = 0;
		ll k, a[100];
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		sort(a, a + n);
		cin >> k;
		cout << binary_search(k, a) << endl;
	}
}

C++: #include <bits/stdc++.h>
テつ?
using namespace std;
テつ?
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ELEM(array) (sizeof (array)/sizeof *(array))
#define MAX_N 100
typedef long long ll;
テつ?
int n = -1;
int a[101];
int k;
テつ?
void serch(int k)
{
テつ?つ?つ?つ?つ?
テつ?つ?つ?つ?nt ans = 1;
テつ?
テつ?つ?つ?つ?nt lb = 0; int ub = n-1;
テつ?つ?つ?つ?hile (ub - lb>1)
テつ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?nt mid = (lb + ub) / 2;
テつ?つ?つ?つ?つ?つ?つ?つ?f (a[mid] == k) {
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?ns++; break;
テつ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?lse if (a[mid] > k){
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?b = mid;
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?ns++;
テつ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?lse {
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?b = mid;
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?ns++;
テつ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?
テつ?つ?つ?つ?out <<ans << endl;
テつ?つ?つ?つ?つ?
テつ?つ?つ?つ?eturn;
}
int main()
{
テつ?つ?つ?つ?hile (cin>>n&& n!=0)
テつ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?EP(i, n){
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?in >> a[i];
テつ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?in >> k;
テつ?つ?つ?つ?つ?つ?つ?つ?erch(k);
テつ?つ?つ?つ?
テつ?
テつ?
テつ?つ?つ?つ?eturn 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

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

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, ans, a[1000], res;

int main(){
	while (cin >> n&&n){
		res = 0;
		fill(a, a + 1000, 0);
		REP(i, n)cin >> a[i];
		cin >> ans;
		int lb = -1, ub = n;
		while (ub - lb > 1){
			/*cout << ub << " " << lb << endl;*/
			res++;
			int mid = (ub + lb) / 2;
			if (a[mid] < ans){
				lb = mid;
			}
			else{
				ub = mid;
			}
		}
		cout << res << endl;
	}
}

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

int n,k;
int* a;

int binary_search(){
	int l=0,r=n-1;
	int ans = 0;
	while(l<=r){
		int m = (l+r)/2;
		if(ans++,k == a[m])
			break;
		else if(k>a[m])
			l = m+1;
		else
			r = m-1;
	}
	return ans;
}

int main(){
	while(true){
		cin >> n;
		if(!n)
			return 0;
		a = new int[n];
		for(int i=0; i<n; i++)
			cin >> a[i];
		cin >> k;
		cout << binary_search() << endl;
		delete[] a;
	}
}

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

int search2(int,int,int,int[],int);

int main() {
	// your code goes here
	int n,low,high,mid,number,ans;
	int num[110]={};
	for(;;){
	cin>>n;
	if(n==0){
		break;
	}
	for(int i=0;i<110;i++){
		num[i]=0;
	}
	for(int i=0;i<n;i++){
		cin>>num[i];
	}
	cin>>number;
	sort(num,num+n);
	int ans=0;
	ans = search2(0,n,number,num,ans);
	cout<<ans<<endl;
	}
	return 0;
}

int search2(int low,int high,int number,int num[],int ans){
	ans++;
	int mid=(low+high)/2;
	if(num[mid]==number||low==(high)){
		return ans;
	}else if(num[mid]<number){
		low=mid+1;
		search2(low,high,number,num,ans);
	}else if(num[mid]>number){
		high=mid;
		search2(low,high,number,num,ans);
	}
	
	
}

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 ans = 0;
	int e = n - 1, s = 0;
	int p = (e - s) / 2;

	while (s <= e){
	    ans++;
	    if (inp[p] == search) break;
	    if (inp[p] > search) e = p - 1;
	    else s = p + 1;

	    p = (s + e) / 2;
	}

	cout << ans << endl;
    }
}

C++: #include<iostream>
using namespace std;
int s[100],ans;
int ok(int c){
  if(s[c]==ans) return 1;
  else if(s[c]<ans) return 2;
  else if(s[c]>ans) return 3;
} 
int main(){
  int n,max,min,count;
  while(cin>>n){
    if(n==0) break;
    count=0;
    for(int i=0;i<n;i++) cin >> s[i];
    cin >> ans;
    min = 0;
    max = 6;
    while(1){
      count++;
      if(ok((min+max)/2)==1){
	cout << count << endl;
	break;
      }
      else if(ok((min+max)/2)==2) min=(min+max)/2+1;
      else max=(min+max)/2-1;
      if(max<min){
	cout << count << endl;
	break;
      }
    }
  }
  return 0;
}

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

int bin_search(int x[],int size,int key)
{
	int low = 0,high = size;
	int count=1;
	while(low < high){
		int mid = (low+high)/2;
		if(x[mid] == key)
			return count;
		else if(x[mid] > key)
			high = mid-1;
		else
			low = mid+1;
		count++;
	}
	return count;
}
int main()
{
	int size;
	int key;
	int x[101];
	while(cin >> size){
		if(size == 0)
			break;
		for(int i=0;i<size;i++){
			cin >> x[i];
		}
		cin >> key;
		cout << bin_search(x,size,key) << endl;
	}
	return 0;
}