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<stdio.h>
int main()
{
	int n,i,a[100],l,m,r,x,c;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;++i)scanf("%d",&a[i]);
		scanf("%d",&x);
		for(c=l=0,r=n-1;l<=r;)
		{
			++c;
			m=(l+r)/2;
			if(a[m]==x)break;
			else if(a[m]<x) l=m+1;
			else r=m-1;
		}
		printf("%d\n",c);
	}
	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){
		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>
using namespace std;

int find( int* a, int s, int e, int d )
{
	int m = ( s + e ) / 2;
	int r = 0;
	if( a[ m ] == d || e - s <= 0 ){
		return 1;
	}
	if( d > a[ m ] ){
		s = m + 1;
	}
	if( d < a[ m ] ){
		e = m - 1;
	}
	return 1 + find( a, s, e, d );
}

int main()
{
	int n;
	while( cin >> n && n ){
		int a[ 100 ] = {0};
		for( int i = 0; i < n; ++i ){
			cin >> a[ i ];
		}
		int d;
		cin >> d;
		cout << find( a, 0, n - 1, d ) << endl;
	}

	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        int num[n],ans;
        for(int i=0;i<n;i++)cin>>num[i];
        cin>>ans;
        int serch=(n-1)/2,kawa[2]={0,n};
        for(int i=1;;i++){
            if(num[serch]==ans||n/2+1==i){
                cout<<i<<endl;
                break;
            }
            else if(num[serch]>ans){
                    kawa[1]=serch;
                    serch=(kawa[0]+kawa[1])/2;
            }
            else {
                    kawa[0]=serch+1;
                    serch=(kawa[0]+kawa[1])/2;
            }
        }
    }
}

C++: #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        int num[n],ans;
        for(int i=0;i<n;i++)cin>>num[i];
        cin>>ans;
        int serch,kawa[2]={0,n-1};
        for(int i=1;;i++){
            serch=(kawa[0]+kawa[1])/2;
            if(num[serch]==ans){
                cout<<i<<endl;
                break;
            }
            if(num[serch]>ans){
                    kawa[1]=serch;
                cout<<kawa[0]<<" "<<kawa[1]<<endl;
            }
            else {
                    kawa[0]=serch+1;
                    cout<<kawa[0]<<" "<<kawa[1]<<endl;
            }
            if(kawa[0]+1==kawa[1]){
                cout<<i<<endl;
                break;
            }
        }
    }
}

C++: #include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
	int n;
	while(cin>>n,n){
		vint v(n);
		rep(i,n) cin>>v[i];
		int a;
		cin>>a;
		int l=0;
		int r=n-1;
		int ans=0;
		while(1){
			if(l>r) break;
			int mid=(l+r)/2;
			ans++;
			if(v[mid]==a){
				break;
			}
			else if(v[mid]<a){
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		cout<<ans<<endl;
	}
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

C++: #include<iostream>
#include<algorithm>
/*
int compare_int(const void* a, const void* b){
	return ( *(int*)a - *(int*)b );
}
*/
int main(){
	int *data, n, key, count, p, l;
	while(true){
		std::cin >> n;
		if(n==0)
			return 0;
		data = new int[n];
		for(int i=0; i<n; i++)
			std::cin >> data[i];
//		std::qsort(data, n, sizeof(int), compare_int);
		std::sort(data,data+n);
		std::cin >> key;
		p=0, l=n-1, count = 0;
		while(true){
			count++;
			if(data[(p+l)/2] == key && p==l)
				break;
			if(p==l)
				break;
			if(data[(p+l)/2] > key)
				p = (p+l)/2+1;
			else
				l = (p+l)/2-1;
		}
		std::cout << count << std::endl;
	}
}

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

int n[101];
int m;
int ans;
int N;

void func(int j,int k){
	if (j>k) {
		return;
	}
	else {
		ans++;
		if (n[(j+k)/2]<m) {
			func((j+k)/2+1,k);
		}
		else if (n[(j+k)/2]>m) {
			func(j,(j+k)/2-1);
		}
	}
	return;
}

	

int main(){
	
	while (1) {
		cin>>N;
		if (N==0) {
			break;
		}
		ans=0;
		for (int i=0; i<N; i++) {
			cin>>n[i];
		}
		cin>>m;
		func(0,N-1);
		cout << ans << endl;
	}
	
}

C++: #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        int num[n],ans;
        for(int i=0;i<n;i++)cin>>num[i];
        cin>>ans;
        int serch,kawa[2]={0,n-1};
        for(int i=1;;i++){
            serch=(kawa[0]+kawa[1])/2;
            if(num[serch]==ans||kawa[0]==kawa[1]){
                cout<<i<<endl;
                break;
            }
            if(num[serch]>ans)kawa[1]=serch-1;
            else kawa[0]=serch+1;
        }
    }
}