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

int n,k;
int a[100001];

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

C++: #include <iostream>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
int A[100];
int main() {
  while(true) {
    int N; cin >> N;
    if(N == 0) break;
    REP(i,N) cin >> A[i];
    int t; cin >> t;
    int lb = 0, ub = N - 1;
    int c = 1;
    while(ub > lb) {
      int mid = (lb + ub) / 2;
      ++c;
      if(A[mid] == t) {
        break;
      }
      if(t < A[mid]) {
        ub = mid - 1;
      }
      else {
        lb = mid + 1;
      }
    }
    cout << c << endl;
  }
}

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

using namespace std;

const int MAX = 128;
int data[MAX];
int n;
int ans;
int wanted;

void solve(){
  int start = 1;
  int end = n;
  sort(data,data+n);
  while(1){
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start >= end) break;
    if(data[now] > wanted) end = now-1;
    else start=now+1;
  }
}

int main(){
  while(cin >> n && n){
    ans = 0;
    for(int i = 1; i <= n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  return 0;
}

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

const int MAX_N = 100;
int values[MAX_N];

int main(){
	int n;
	while(scanf("%d", &n), n != 0){
		// target: 探す値, ans: 探索が終わるまでの比較回数
		int target, ans = 0;
		// 二分探索の範囲
		int l = -1, r = n;
		
		memset(values, 0, sizeof(values));
		for (int i = 0; i < n; i++) {
			scanf("%d", &values[i]);
		}
		scanf("%d", &target);
		
		while(r - l > 1) {
			ans++;
			int m = (l + r) / 2;
			if (values[m] == target) break;
			else if (values[m] < target) l = m;
			else r = m;
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

using namespace std;

const int MAX = 101;
int data[MAX];
int n;
int ans;
int wanted;

void solve(){
  int start = 0;
  int end = n-1;
  //sort(data,data+n);
  while(1){
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start >= end) break;
    if(data[now] > wanted) end = now;
    else start=now+1;
  }
}

int main(){
  while(cin >> n && n){
    ans = 0;
    for(int i = 0; i < n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  return 0;
}

C++: #include <stdio.h>

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

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cmath>
#include <queue>

using namespace std;

int a[100000];
int lef;
int rig;

int ans;

bool binary_search_2(int num){
	if(lef == rig){
		ans++;
		return false;
	}
	int middle = (lef + rig) / 2;
	ans++;
	if(a[middle] > num){
		rig = middle - 1;
		binary_search_2(num);
	}else if(a[middle] < num){
		lef = middle + 1;
		binary_search_2(num);
	}else if(a[middle] == num){
		return true;
	}
}

bool binary_search(int num, int n){
	lef = 0;
	rig = n - 1;
	binary_search_2(num);
}

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

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

using namespace std;

int s[100010],t[50010];
int n, q, ans = 0;

bool binary_search(int x) {
	int l = 0, r = n;
	ans = 0;
	while (r - l >= 1) {
		int m = (l + r) / 2;
		ans++;
		if (s[m] == x)return true;
		else if (s[m] > x) {
			r = m;
		}
		else if (s[m] < x) {
			l = m+1;
		}
	}
	ans++;
	return false;
}
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) {
			cin >> s[i];
		}
		cin >> t[0];
		binary_search(t[0]);
		for (int i = 0; i < n; i++) {
			s[i] = 0;
		}
			cout << ans << endl;
	}
	return 0;
}

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 *s = inp, *e = inp + n - 1, *p = inp + n/2;
	int ans = 0;
	int b = 0;
	while (1){
	    ans++;
	    if (p == s && p == e) break;
	    if (*p == search) break;
	    else if (*p > search){
		e = p-1;
		p = s + (e - s)/2;
	    }
	    else if (*p < search){
		s = p+1;
		p = s + (e - s)/2 + 1;
	    }
	}

	cout << ans << endl;
    }
}

C++: #include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main() {
	int n, x;
	while (1) {
		cin >> n;
		if (n == 0) break;
		vi d(n);
		rep(i, 0, n) {
			cin >> d[i];
		}
		cin >> x;
		int cnt = 0, l = 0, r = n - 1;
		while (r - l > 0) {
			int mid = (l + r) / 2;
			cnt++;
			if (d[mid] > x) {
				r = mid - 1;
			}
			else if (d[mid] < x) {
				l = mid + 1;
			}
			else if (d[mid] == x) {
				break;
			}
		}
		cout << cnt+1 << 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;
        }
    }
}