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>
#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 (l<=r) {
			cnt++;
			int mid = (l + r) / 2;
			if (d[mid] > x) {
				r = mid - 1;
			}
			else if (d[mid] < x) {
				l = mid + 1;
			}
			else if(d[mid]==x){
				break;
			}
		}
		cout << cnt << endl;
	}
}

C++: #include <iostream>
#include <vector>
//#include <fstream>

using namespace std;

int main()
{
//	cut here before submit 
//	freopen ("testcase.search3", "r", stdin );
	int n;

	while (1){
		cin >> n;

		if (!n ){
			break;
		} // end if

		vector <int> a (n, 0 );
		for (int i = 0; i < n; ++i){
			cin >> a[i];
		} // end for

		int key;
		cin >> key;
		int first = 0, last = n - 1, mid;
		int res = 0;

		do{
			mid = (first + last)/2;		
			++res;
			if (a[mid] < key ){
				first = mid + 1;
			}else if (a[mid] > key ){
				last = mid - 1;
			}else{
				break;
			} // end if
		}while (first <= last ); // end while

		cout << res << endl;	
		
	} // end loop
		
	return 0;
}

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;
			if(up < low) break;
		}
		cout << cnt << endl;
	}
	return 0;
}

C++: #include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

////////////////*My library*////////////////////////
#define rep_to(a,i,n) for(i=a;i<n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define rep_r(i,n) for(i=n-1;i>=0;i--)
#define debug_i(x) printf("x:%d\n",x)
#define debug_f(x) printf("x:%f\n",x)
#define debug_s(str) printf("str:%s\n",str)
#define debug_c(c) printf("c:%c\n",c)
#define s_i1(x) scanf("%d",&x)
#define s_i2(x,y) scanf("%d %d",&x,&y)
#define s_i3(x,y,z) scanf("%d %d %d",&x,&y,&z)
////////////////////////////////////////////////////
////////////////////////
/*prime()*/
/*primecount()*/
/*sort()*/
///////////////////////
int main()
{
	int i,j;
	int n,num[100000]={},key;

	while(1)
	{
		s_i1(n);
		if(n==0)break;
		rep(i,n)s_i1(num[i]);
		s_i1(key);

	/////????????¢?´¢//////////////////

		int min=0;
		int max=n-1;
		int mid=(min+max)/2;
		int count=0;
		while(1)
		{
			count++;
			mid=(min+max)/2;
			if(min==max)break;
			//else if(key!=num[mid] && min==max)break;
			else if(key>num[mid])min=mid+1;
			else if(key<num[mid])max=mid-1;
		}
	///////////////////////////////
	printf("%d\n",count);
	}
return 0;
}

C++: /* {{{ Shinobu kawaii */
/*
  ______   __        _                  __                 
.' ____ \ [  |      (_)                [  |                
| (___ \_| | |--.   __   _ .--.   .--.  | |.--.   __   _   
 _.____`.  | .-. | [  | [ `.-. |/ .'`\ \| '/'`\ \[  | | |  
| \____) | | | | |  | |  | | | || \__. ||  \__/ | | \_/ |, 
 \______.'[___]|__][___][___||__]'.__.'[__;.__.'  '.__.'_/ 
                                                           
*/
/* }}} */

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

// #define int long long

/* cpp template {{{ */

/* short */
#define pb push_back
#define mp make_pair
#define print(x) cout << x << '\n'
#define Fi first
#define Se second

/* REPmacro */
#define REPS(i, a, n) for (int i = (a); i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = 1; i <= (n); i++)
#define DEPS(i, a, n) for (int i = (a); i >= n; i--)
#define DEP(i, n) for (int i = (n); i >= 0; i--)

/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;

/* const */
const int INF = 999999999;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

/* func */
inline bool is_uruu(int y) {return (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0));}
inline bool inside(int y, int x, int H, int W) {return (y >= 0 && x >= 0 && y < H && x < W);}

/* }}} */

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  for (int n; cin >> n, n;){
    vi a(n); REP(i, n) cin >> a[i];
    int ans; cin >> ans;
    int mid, l = 0, r = n - 1;
    int cnt = 1;
    while (l != r){
      mid = (l + r) / 2;
      if (a[mid] == ans){
        break;
      }
      if (a[mid] < ans){
        l = mid + 1;
      } else {
        r = mid;
      }
      cnt++;
    }
    print(cnt);
  }

  return (0);
}

C++: #include<iostream>
using namespace std;
int a[100];
int main(){
	int n,key;
	while(true){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++)cin>>a[i];
		cin>>key;
		int ans=1;
		int left=0,right=n,mid;
		while(true){
			if(left>=right-1)break;
			mid=(left+right)/2;
			if(a[mid]==key)break;
			if(a[mid]<key)left=mid;
			if(a[mid]>key)right=mid;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int n;
	cin >> n;
	vector<int> a(n);
	if(n == 0) break;
	REP(i,n) cin >> a[i];
	int num;
	cin >> num;
	int l,m,h,ans;
	h = n;
	l = 0;
	m = (h+l)/2;
	ans = 0;
	while(true){
	    if(a[m] > num){
		if(h-l == 1){
		    ans++;
		    break;
		}else if(h-l==0){
		    break;
		}
		h = m;
	    }else if (a[m] < num){
		if(h-l == 1){
		    ans++;
		    break;
		}else if(h-l==0){
		    break;
		}
		l = m;
	    }else{
		ans++;
		break;
	    }
	    m = (h+l)/2;
	    ans++;
	}
	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 = 0;
		while (1){
			
			if (max == min){
				ans++;
				break;
			}
			
			i = (max + min) / 2;
			if (x[i] < obj){
				min = i + 1;
			}else if (x[i] > obj){
				max = i - 1;
			}else{
				break;
			}
			
			ans++;
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}

C++: #include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
	while (1) {
		long long n, a[110], k, ans, r, l;
		ans = 0;
		cin >> n;
		if (n == 0) {
			break;
		}
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		cin >> k;
		r = n-1;
		l = 0;
		while (r - l >= 0) {
			ans++;
			long long m = (l + r) / 2;
			if (a[m] == k) {
				break;
			}
			else if (a[m] > k) {
				r = m - 1;
			}
			else if (a[m] < k) {
				l = m + 1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}