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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,s;
  while(cin >> n&&n){
    vary(int,v,n+1,0);
    rep(i,n+1){
      cin >> v[i];
    }
    int lb = 0,ub = n-1;
    int ans = 0;
    while(1){
      int mid = (lb+ub)/2;
//       debug(v[mid]);
      ++ans;
      if(mid == ub || v[n] == v[mid]){
        break;
      }
      if(v[mid] < v[n]){
        lb = mid+1;
      }
      else{
        ub = mid;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

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

int v[100];

int main() {
    int n;
    while (cin >> n, n) {
        for (int i=0; i<n; ++i) {
            cin >> v[i];
        }
        int search;
        cin >> search;
        int l = 0, h = n-1, res = 0;
        while (l <= h) {
            int mid = (l + h) / 2;
            ++ res;
            if (mid == search) {
                break;
            } else if (search < mid) {
                h = mid-1;
            } else {
                l = mid+1;
            }
        }
        cout << res << endl;
    }
    return 0;
}

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)l=m+1;
            else if(a[m]<k)f=m-1;
            else break;
        }
        cout<<cnt<<endl;
    }
}

C++: #include<stdio.h>

int main(void)
{
	int x[100];
	int st,fn,a,n,i,ty,kai;
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		kai=1;  st=0; fn=n-1;
		for(i=0;i<n;i++) scanf("%d",&x[i]);
		scanf("%d",&a);
		while(a!=x[ty]||st!=fn){
			ty=(st+fn)/2;
			if(a==x[ty]||st==fn)break;
			else if(a>x[ty])  st=ty+1;
			else fn= ty-1;
			kai++;
		}
		printf("%d\n",kai);
	}
	return 0;
}

C++: #include <cstdio>
#define buf 1000001
using namespace std;
int cnt,b[buf];
void binary_search(int d,int a);

int main(void){
  int i,j,a,n;
  char str[200];

  for( ; ; ){
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&a);
    if(a==0) break;
    for(i=0;i<a;i++){
      fgets(str,sizeof(str),stdin);
      sscanf(str,"%d",&n);
      b[i]=n;
    }
    for(i=0;i<a;i++)
      printf("%d ",b[i]);
    printf("\n");
    cnt=1;
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&n);
    binary_search(n,a);
    printf("%d\n",cnt);
  }
  return 0;
}

void binary_search(int n,int a){
  int left,right,mid;
  left = 0; right = a;
  while(left < right){
    mid = (left + right)/2;
    if(b[mid] == n)
      break;
    else if(n < b[mid])
      right = mid;
    else if(n > b[mid])
      left = mid+1;
    cnt++;
  }
}

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

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

void func(int j,int k){
 ans++;
 if (n[(j+k)/2]==m||j>=k) {
  return;
 }
 else {
  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;
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-1;
		int cnt = 1;
		while(l != r){
			int med = (l+r)/2;
			if(array[med] > M)r = med-1;
			else l = med+1;
			cnt++;
		}
		printf("%d\n",cnt);
	}
    return 0;
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,s;
  while(cin >> n&&n){
    vary(int,v,n+5,0);
    rep(i,n+1){
      cin >> v[i];
    }
    int lb = 0,ub = n-1;
    int ans = 0;
//     debug(v[n]);
    while(1){
      int mid = (lb+ub)/2;
//       debug(mid);
      ++ans;
      if(mid == ub){
        break;
      }
      if( v[n] == v[mid]) break;
      if(v[mid] < v[n]){
        lb = mid+1;
      }
      else{
        ub = mid-1;
      }
    }
    cout << ans << endl;
  }
  return 0;
}