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 <string>

#define ARRAY_SIZE 100

int binary_search(int a[], int n, int x) {
  int l = 0, r = n + 1, search_count = 0;
  int res = -1;
  while ( l <= r ) {
    int mid = (l + r) / 2;
    if (x < a[mid]) {
      res = mid;
      r   = mid - 1;
    } else {
      l = mid + 1;
    }
    search_count++;
  }
  return search_count;
}

int main() {

  int num, search_num;
  int array[ARRAY_SIZE];

  std::cin >> num;
  while ( num != 0 ) {
    for (int i = 0; i < num; i++) {
      std::cin >> array[i];
    }
    std::cin >> search_num;

    std::cout << binary_search(array, num, search_num) << std::endl;

    std::cin >> num;
  }

}

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

int main(){
	int n,key,a[101];
	while( cin >> n , n ){
		for(int i=0 ; i<n ; ++i ){
			cin >> a[i];
		}
		cin >> key;
		bool flag = true;
		int begin = 0;
		int end = n-1;
		int cnt = 1;
		for( ; flag && begin != end ; ++cnt ){
			int pos = (begin+end)/2;
			int val = a[pos];
			if( key == val ){
				flag = false;
			}else{
				if( key < val ){
					end = pos-1;
				}else{
					begin = pos+1;
				}
			}
		}
		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) {
			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;

int main() {
  int hi,lo,m,n,a,i,k,d[100];
  while(cin >> n && n!=0) {
	  for (i=0;i<n;i++) cin >> d[i];
	  cin >> a;
	  hi=n-1; lo=k=0;
	  while(true) {
	  k++; m=(hi+lo)/2; 
	  if (d[m]>a) hi=m-1; else if (d[m]<a) lo=m+1; else break;
	  if (hi==lo) { k++; break;}
	   }
	  cout << k << endl;
  }
  return 0;
}

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<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

int a[200];
int main() {
	int n;
	while (scanf("%d", &n), n) {
		rep(i, n)scanf("%d", &a[i]);
		int search; scanf("%d", &search);
		int s = 0, g = n - 1;
		int cnt = 0;
		while (s <= g) {
			cnt++;
			if (a[(s + g) / 2] == search)break;
			if (a[(s + g) / 2] < search)s = (s + g) / 2 + 1;
			else g = (s + g) / 2 - 1;
		}
		printf("%d\n", cnt);
	}
}

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

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

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n;
	while(cin >> n , n){
		int need , ans = 0;
		vector<int> d(n);
		rep(i,n) cin >> d[i];
		
		cin >> need;
		int l = 0 , r = n-1 , m;
		do{
			ans++;
			m = (l+r)/2;
			if(d[m] > need) r = m-1;
			else if(d[m] < need) l = m+1;
		}while(need != d[m] && m != r && m != l);
		cout << ans << endl;
	}
}

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<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

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

int main(void) {
  int i,j;
  int n;
  while(1){
    cin>>n;
    if(n==0)break;
    vi a(n);
    rep(i,n)
      cin>>a[i];
    int k;
    cin>>k;
    int right=n-1,left=0;
    rep(i,n){
      if(right==left)break;
      int c=(right+left)/2;
      if(a[c]==k)break;
      if(a[c]<k)
        left=c+1;
      else
        right=c-1;
    }
  cout<<i+1<<endl;
  }
}