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;
int a[100];
int n,k;
main()
{
    while(cin>>n,n)
    {
        for(int i=0;i<n;i++)cin>>a[i];
        int l=0,f=n-1;
        cin>>k;
        int cnt=0;
        while(f>=l)
        {
            int m=(f+l)/2;
            cnt++;
            if(a[m]>k)f=m-1;
            else if(a[m]<k)l=m+1;
            else break;
        }
        cout<<cnt<<endl;
    }
}

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

using namespace std;

int search(int& target, vector<int>& data, int l, int r, int count)
{
	if(l > r)
	{
		return(count);
	}
	++count;
	int pos = (l + r) / 2;	
	if(data[pos] == target)
	{
		return(count);
	}
	else if(data[pos] < target)
	{
		return(search(target, data, pos + 1, r, count));
	}
	else
	{
		return(search(target, data, l, pos - 1, count));
	}
}

void solve()
{
	int n;
	while(cin >> n, n)
	{
		vector<int> data(n);
		for(int i = 0; i < n; ++i)
		{
			cin >> data[i];
		}
		int target;
		cin >> target;
		cout << search(target, data, 0, data.size() - 1, 0) << endl;
	}
}

int main()
{
	solve();
	return(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-1){
		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 <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 1145141919
#define MOD 1000000007
#define ALL(a) begin((a)),end((a))
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
typedef vector<edge> edges;
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

vi v;
int cnt;

void solve(int lb, int ub, int k)
{
	while (ub-lb>1)
	{
		cnt++;
		int mid = (lb + ub) / 2;
		if (v[mid] == k) return;
		if (v[mid] > k) ub = mid;
		else lb = mid;
	}
}

int main()
{
	int n;
	while (cin >> n, n)
	{
		v.clear();
		cnt = 0;
		REP(i, n)
		{
			int a;
			cin >> a;
			v.push_back(a);
		}
		int k; cin >> k;
		solve(-1, n, k);
		cout << cnt << endl;
	}
	return 0;
}

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

using namespace std;

int main(){

	int n;
	while(cin>>n&&n!=0){
		vector<int> nums;
		int t;
		for(int i = 0; i < n; i++){
			cin>>t;
			nums.push_back(t);
		}
		int s;
		cin>>s;
		int ub=n-1;
		int lb=0;
		int cnt=0;
		while(1){
			int mid=ub+lb;
			mid/=2;
			cnt++;
			if(nums[mid]==s||ub==lb){
				break;
			}
			else if(nums[mid]>s){
				ub=mid-1;
			}
			else if(nums[mid]<s){
				lb=mid+1;
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}

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

int main()
{
  int n;
  while (cin >> n) {
    if (n == 0)
      break;

    vector<int> array(n);
    for (int i = 0; i < n; ++i)
      cin >> array[i];

    int target;
    cin >> target;

    int ans = 0, low = 0, high = n-1;
    while (low <= high) {
      ++ans;
      int mid = (low + high) / 2;
      if (array[mid] == target)
	break;
      else if (array[mid] < target)
	low = mid+1;
      else
	high = mid-1;
    }
    cout << ans << endl;
  }
  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){
    int now = (start+end)/2;
    if(data[now] == wanted || start >= end) break;
    if(data[now] > wanted) end = now-1;
    else start=now+1;
    ans++;
  }

}

int main(){
  while(cin >> n && n){
    ans = 1;
    for(int i = 0; i < n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  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) {
    int mid = (ub+lb)/2;
    //printf("lb=%d ub=%d mid=%d\n", lb, ub, mid);
    if (l[mid] < t) {
      if (mid != ub) lb = mid + 1;
      else break;
    }
    else  if (l[mid] > t) {
      if (mid != 0) ub = mid - 1;
      else break;
    } else {
      break;
    }
    res++;
  }

  cout<<res<<endl;
}

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

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

using namespace std;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		vector<int> data(n);
		int left = 0;
		int right = n-1;
		for (int i = 0; i < n; i++) {
			cin >> data[i];
		}
		int counter = 0;
		int tansa;
		cin >> tansa;
		while (true) {
			int half = (left+right) / 2;
			counter++;
			if (left >= right) {
				break;
			}
			if (data[half] == tansa) {
				break;
			} else if (data[half] < tansa) {
				left = half+1;
			} else {
				right = half-1;
			}
		}
		cout << counter << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main()
{
	for(int n;scanf("%d",&n),n;){
		vi a(n);
		rep(i,n)
			scanf("%d",&a[i]);
		int key;
		scanf("%d",&key);
		
		int res=0;
		int left=0,right=n-1;
		while(left<=right){
			res++;
			int center=(left+right)/2;
			if(a[center]<key)
				left=center+1;
			else if(a[center]>key)
				right=center-1;
			else
				break;
		}
		printf("%d\n",res);
	}
	
	return 0;
}