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{};
	int cnt{};
	int i{}, j{};
	
	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{};
	int data[100]{};
	int key{};
	
	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 <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||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-1;
		search2(low,high,number,num,ans);
	}
}

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)break;
            if(data[cent]>k){
                right=cent-1;
            }
            if(data[cent]<k){
                left=cent+1;
            }
            
            if( left>right )break;
        }
        cout<<sum<<endl;
    }

    return 0;
}

C++: #include<stdio.h>

int main(void)
{
	int x[100];
	int st,fn,a,n,i,j,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){
			j=(st+fn)/2;
			if(a==x[j]||st==fn)break;
			else if(a>x[j])  st=j+1;
			else fn= j-1;
			kai++;
		}
		printf("%d\n",kai);
	}
	return 0;
}

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 num[101],r[2];
	int kazu, target, t;
	int i;

	while (1){
		t = 0;
		cin >> kazu;

		if (kazu == 0){
			break;
		}

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

		cin >> target;


		r[0] = 0;
		r[1] = (kazu - 1);
		t = 0;
		
		while (1){
			t++;
			if (num[(r[0] + r[1]) / 2] == target){
				break;
			}

			if (r[0] == r[1]){
				break;
			}

			if (num[(r[0] + r[1]) / 2] < target){
				r[0] = (r[0] + r[1]) / 2 + 1;
			}
			else{
				r[1] = (r[0] + r[1]) / 2 - 1;
			}
								
		}


		cout << t << endl;
	}

}

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

int main()
{
	int N;
	while(cin >> N, N)
	{
		int b[100];
		for(int i=0; i<N; i++)
			cin >> b[i];
		
		int s, lo=0, hi=N-1, cnt=1;
		cin >> s;
		
		while(hi>lo)
		{
			int mi=(hi+lo)/2;
			if(b[mi]==s) break;
			
			s>b[mi]?lo=mi+1:hi=mi-1;
			cnt++;
			
		}
		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()
const int MAX = 110;

int main()
{
    int n;
    while(cin >> n && n)
    {
        int num[MAX] = {};
        int des;
        REP(n) cin >> num[i]; 
        cin >> des;

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

        }
        cout << ans << endl;
    }

    return 0;
}

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

int nibn(int a[], int s, int e, int k);
int nibn(int a[], int s, int e, int k){
	if(s>e) return 1;
	if(a[(s+e)/2] == k){
		return 1;
	}
	else if(a[(s+e)/2] < k){
		return 1 + nibn(a,(s+e)/2+1,e,k);
	}
	else if(a[(s+e)/2] > k){
		return 1 + nibn(a,s,(s+e)/2-1,k);
	}
}


int main(){
	int n, a[150], k;
	while(cin >> n){
		if(!n) break;
		ans = 0;
		for(int i = 0;i<n;i++){
			cin >> a[i];
		}
		cin >> k;
		cout << nibn(a,0,n-1,k) << endl;
	}
	return 0;
}