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 <algorithm>
using namespace std;

int T[100010];
int find(int m,int x){
	int r=0,l=m,ans=0;
	while(1){
		ans++;
		if(T[(r+l)/2]==x)return ans;
		else if(r>=l)break;
		if(T[(r+l)/2]>x)l=(r+l)/2-1;
		else if(T[(r+l)/2]<x)r=(r+l)/2+1;
	}
	return ans;
}
int main(){
	int n,k,num,ans;
	while(1){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>T[i];
		}
		cin>>k;
		ans=find(n,k);
		cout<<ans<<endl;
	}
	return 0;
}

C++: #include<stdio.h>
int main(void)
{
	int n,m;
	int a[101];
	int high,low,key;
	int cnt=0;
	int i,j;

	scanf("%d",&n);
	while(n!=0){
		for(i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		scanf("%d",&m);
		cnt=0;
		low=0;
		high=n-1;
		while(high>=low){
			cnt++;
			key=(high+low)/2;
			if(a[key]==m){
				break;
			}
			else if(a[key]>m){
				high=key-1;
			}
			else {
				low=key+1;
			}
		}
		printf("%d\n",cnt);
		scanf("%d",&n);
	}
	return 0;
}

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

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n) REP(i,0,n)

int n, l[100], t;

void solve() {
  rep(i,n) cin>>l[i];
  cin>>t;
  
  int lb = 0, ub = n-1, res = 1;
  while (ub != lb) {
    if (lb > ub) break;
    int mid = (ub+lb)/2;
    //printf("lb=%d ub=%d mid=%d\n", lb, ub, mid);
    
    
    if (l[mid] < t) lb = mid + 1;
    else  if (l[mid] > t) {
      if (mid != 0) ub = mid - 1;
      else ub = mid;
    } else {
      break;
    }
    res++;
  }

  cout<<res<<endl;
}

int main (int argc, char const* argv[]) {
  while (cin>>n, n) {
    solve();
  }
  return 0;
}

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

int main(void){
    int n;
    while(cin >> n, n){
        int data[10000];
        int need;
        for(int i=0; i < n; i++)
            cin >> data[i];
        cin >> need;
        

        int before = 0, after = n-1;
        int cnt = 0;
        while(1){
            int mid = (after + before) / 2;
            cnt++;
            if(need == data[mid])
                break;
            if(before >= after)
                break;
            if(data[mid] > need)
                after = mid;
            else
                before = mid+1;
        }
        cout << cnt << endl;
    }
    return 0;
}

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

int main(){
  int l,r,m,n,a[100],g,c;
  for(;;){
    cin >> n;
    if(!n)break;
    for(int i=0;i<n;i++)cin >> a[i];
    cin >> g;


    l = 0;r = n-1;
    c = 1;
    while(l<r){
      m = (l+r)/2;
      if(a[m]==g)break;
      else if(a[m]>g)r = m-1;
      else l = m+1;
      c++;
    }

    cout << c << endl;
  }
}

C++: #include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef pair<int,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
	int N;
	while(scanf("%d",&N),N){
		int array[128];
		rep(i,N){
			scanf("%d",&array[i]);
		}
		int M;
		scanf("%d",&M);
		int l = 0;
		int r = N;
		int cnt = 1;
		while(l+1 != r){
			int med = (l+r)/2;
			if(array[med] == M)break;
			if(array[med] > M)l = med;
			else r = med;
			cnt++;
		}
		printf("%d\n",cnt);
	}
    return 0;
}

C++: #include <stdio.h>
#include <stack>
#include <math.h>

using namespace std;

struct Info{
	int id,sum;
};

int main(){

   int n,k,table[100],left,right,count,m;

   while(true){
	   scanf("%d",&n);
	   if(n == 0)break;

	   for(int i=0; i < n; i++)scanf("%d",&table[i]);

	   scanf("%d",&k);

	   count = 0;
	   left = 0,right = n-1;
	   m = (left+right)/2;
	   while(left <= right){
		   count++;
		   if(table[m] == k)break;
		   else{
			   if(table[m] < k){
				   left = m+1;
				   m = (left+right)/2;
			   }else{
				   right = m-1;
				   m = (left+right)/2;
			   }
		   }
	   }

	   printf("%d\n",count);

   }

    return 0;
}

C++: #define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 29;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;
const int CLK = CLOCKS_PER_SEC;

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)

int nums[100];

int main(){
	int n, p;
	while(cin >> n && n){
		rep(i, n){
			cin >> nums[i];
		}
		cin >> p;
		int l = 0, r = n;
		int res = 0;
		while(r - l > 1){
			res++;
			int mb = (l + r) / 2;
			if(nums[mb]==p) break;
			else if(nums[mb] < p) r = mb;
			else l = mb + 1;
		}
		cout << res + 1 << 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;
		int flag=0;
		while(1)
		{
			count++;
			mid=(min+max)/2;
			if(key==num[mid])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++: #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);
}