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>
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(head >= tail){
		return count;
	}else{
		if(array[head + (tail-head)/2] == key){
			return count;
		}else{
			if(array[head + (tail-head)/2] > key){
				return BS(key, array, head, (tail-head)/2-1+head, count);
			}else{
				return BS(key, array, (tail-head)/2+1+head, 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];
		}
		cin >> key;
		
		bubble(N, data);
		
		cout << BS(key, data, 0, N, 0) << endl;
		
		for(int i=0;i<N;++i){
			data[i] = 0;
		}
	}
}

C++: #include <stdio.h>

int main(void)
{
	int n;
	int x[100];
	int i,j;
	int max, min;
	int obj;
	int ans;
	
	while (1){
		scanf("%d", &n);
		
		if (n == 0)break;
		
		for (i = 0; i < n; i++){
			scanf("%d", &x[i]);
		}
		
		for (i = 0; i < n; i++){
			for (j = 0; j < n; j++){
				if (x[i] > x[j]){
					x[i] += x[j];
					x[j] = x[i] - x[j];
					x[i] -= x[j];
				}
			}
		}
		
		scanf("%d", &obj);
		
		max = n - 1;
		min = 0;
		ans = 0;
		while (1){
			
			i = (max + min) / 2;
			if (x[i] < obj){
				min = i + 1;
			}
			else if (x[i] > obj){
				max = i - 1;
			}
			else{
				break;
			}
			
			ans++;
			
			if (max == min){
				ans++;
				break;
			}
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}

C++: #include <stdio.h>
int n, a[100], t;
int main() {
	while(true) {
		scanf("%d", &n);
		if(n == 0) break;
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		scanf("%d", &t);
		int c = 0;
		int l = 0;
		int r = n - 1;
		while(r - l > 1) {
			int m = (l + r) / 2; c++;
			if(a[m] == t) break;
			if(a[m] < t) {
				l = m + 1;
			}
			else {
				r = m - 1;
			}
		}
		printf("%d\n", c);
	}
	return 0;
}

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

int main() {
    int N;
    while (cin >> N, N) {
        vector<int> v(N);
        for (auto& i : v) cin >> i;

        int x;
        cin >> x;
        int l = 0, r = N - 1;

        int count = 0;
        while (true) {
            int m = (r + l) / 2;
            count++;
            if (v[m] == x) break;

            if (v[m] < x) {
                l = m + 1;
            } else {
                r = m - 1;
            }

            if (l > r) break;
        }

        cout << count << endl;
    }

    return 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 (true) {
			int m = (l + r) / 2;
			c++;
			
			if (a[m] == k) break;
			if (r == l) break;
			
			if (a[m] < k) l = m + 1;
			else r = m - 1;
		}
		
		cout << c << endl;
	}
	return 0;
}

C++: #include <cstdio>
#include <cmath>
#define buf 1000001
using namespace std;
int cnt,b[buf]={0};
void binary_search(int d,int a);

int main(void){
  int i,j,a,n;
  char str[200];

  for( ; ; ){
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&a);
    if(a==0) break;
    for(i=0;i<a;i++){
      fgets(str,sizeof(str),stdin);
      sscanf(str,"%d",&n);
      b[i]=n;
    }
    cnt=1;
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&n);
    binary_search(n,a);
    printf("%d\n",cnt);
  }
  return 0;
}

void binary_search(int n,int a){
  int left,right,mid;
  double tmp;
  left = 0; right = a-1;
  while(left < right){
    tmp = floor((left + right)/2);
    mid=tmp;
    if(b[mid] == n)
      break;
    else if(n < b[mid])
      right = mid;
    else if(n > b[mid])
      left = mid+1;
    cnt++;
  }
}

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]||fn-st==0)break;
			else if(fn-st<0){kai--;break;}
			else if(a>x[ty])  st=ty+1;
			else fn= ty-1;
			kai++;
		}
		printf("%d\n",kai);
	}
	return 0;
}

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

int main()
{
	int array[1000];
	int n;
	
	while (scanf("%d", &n), n){
		for (int i = 0; i < n; i++){
			scanf("%d", &array[i]);
		}
		
		int q;
		scanf("%d", &q);
		
		int l = 0;
		int r = n - 1;
		int cnt = 0;
		while (1){
			int m = (l + r) / 2;
			
			cnt++;
			
			if (q == array[m]){
				break;
			}
			
			else if (l == r){
				break;
			}
			
			else if (q < array[m]){
				r = m - 1;
				if (r < l){
					r = l;
				}
			}
			
			else if (q > array[m]){
				l = m + 1;
				if (l > r){
					l = r;
				}
			}
		}
		
		printf("%d\n", cnt);
	}
	
	return 0;
}

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

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

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

    cout << cnt << endl;
  }

}

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

using namespace std;

int main(){

	int n;

	while(true){
		cin >> n;
		if(n == 0){
			break ;
		}

		int num[128];
		for(int i = 0; i < n; i++){
			cin >> num[i];
		}
	

		int want ;
		cin >> want ;

		int t,l,c,count ;
		t = 0 ;
		l = n - 1 ;

		for( count = 0; t <= l; count++){
			c = (t + l)/2 ;
			cout << t << " " << c << " " << l << endl;
			if( want > num[c] ){
				t = c + 1;
			} else if( want < num[c]){
				l = c - 1 ;
			} else {
				count++;
				break ;
			}
		}

		cout << count << endl ;
	}
	return 0;
}

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

int main(){
	int *data, n, key, count, p, l, c;
	while(true){
		std::cin >> n;
		if(n==0)
			return 0;
		data = new int[n];
		for(int i=0; i<n; i++)
			std::cin >> data[i];
		std::sort(data, data+n);
		std::cin >> key;
		p=0, l=n-1,count = 0;
		while(p<=l){
			count++;
			c = (p+l)/2;
			if(data[c] == key && p==l)
				break;
			if(data[c] > key)
				p = c+1;
			else
				l = c-1;
		}
		std::cout << count << std::endl;
		delete[] data;
	}
}