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

void search(int times);
void twice(int data[],int t, int target, int count);

void search(int times){
	int data[times] = {0};
	int target, count=0;
	for(int i=0;i<times;i++){
		cin >> data[i];
	}
	cin >> target;
	

	return twice(data, times, target, count);
}

void twice(int data[],int t, int target, int count){
	
	if(t == 1/* || t == 0*/){
		count++;
		cout << count <<endl;
	} else if(t == 2){
		if(data[0] == target || data[1] == target){
			count++;
			cout << count << endl;
		} else {
			count = count + 2;
			cout << count <<endl;
		}
	} else {
	
	int times = t/2;
	if(data[times] < target){
		int dataN[times] = {};
		for(int i=0;i<times;i++){
			if(t % 2 == 1){
				dataN[i]=data[i+times+1];
			} else if(t % 2 == 0){
				dataN[i] = data[i+times];
			}
		}

		count++;
		twice(dataN,times, target, count);

	} else if(data[times] > target){
		int dataN[times] = {};
		for(int i=0;i<times;i++){
			dataN[i]=data[i];
		}
		count++;
		twice(dataN,times, target, count);
	} else if(data[times] == target){
		count++;
		cout << count << endl;
	}
}
}

int main() {
	int i;
	while(1) {
		cin >> i;
		//cout << res << endl;
		if(i == 0){
			break;
		}

		search(i);
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define mem(a) memset(a,0,sizeof(a))
#define pd(a) printf("%.10f\n",a)
#define pb(a) push_back(a)
#define in(a) insert(a)
#define pi M_PI
#define R cin>>
#define F first
#define S second
#define C class
#define ll long long
#define ln cout<<'\n'
#define _(_1,_2,_3,N,...)N
#define pr(...) _(__VA_ARGS__,pr3,pr2,pr1)(__VA_ARGS__)
template<C T>void pr1(T a){cout<<a;ln;}
template<C T,C T2>void pr2(T a,T2 b){cout<<a<<' '<<b;ln;}
template<C T,C T2,C T3>void pr3(T a,T2 b,T3 c){cout<<a<<' '<<b<<' '<<c;ln;}
template<C T>void PR(T a,int n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int n;
  while(R n && n) {
    int a[n];
    rep(i,n) R a[i];
    int x;
    R x;
    int l=0,r=n-1,c=0;
    while(l<=r) {
      int m=(l+r)/2;
      c++;
      if(a[m]==x) break;
      else if(a[m]<x) l=m+1;
      else r=m-1;
    }
    pr(c);
  }
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  Main();return 0;
}

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


int main() {
	while (1) {
		int N; cin >> N;
		if (!N)break;
		vector<int>vs(N);
		for (int i = 0; i < N; ++i)cin >> vs[i];
		int K; cin >> K;
		int amin = 0;
		int amax = N-1;
		int ans = 0;
		while (amin <=amax) {
			ans++;
			const int amid = (amin + amax) / 2;
			if (vs[amid] < K) {
				amin = amid+1;
			}
			else if (vs[amid] == K) {
				break;
			}
			else {
				amax = amid-1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

C++: // 2011/08/24 Tazoe

#include <iostream>
using namespace std;

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

		int data[100];
		for(int i=0; i<n; i++)
			cin >> data[i];

		int key;
		cin >> key;

		int cnt = 0;
		int left  = 0;
		int right = n-1;
		while(left<=right){
			int middle = (left+right)/2;
			cnt++;
			if(key==data[middle])
				break;
			else if(key<data[middle])
				right = middle-1;
			else
				left  = middle+1;
		}

		cout << cnt << endl;
	}

	return 0;
}

C++: #include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	for (int n; cin >> n&&n;) {
		vector<int> a(n);
		rep(i, 0, n)cin >> a[i];
		int s; cin >> s;
		int l = 0, r = n - 1;
		int cnt = 0;
		while (true) {
			cnt++;
			if (r - l == 0)break;
			int m = (l + r) / 2;
			//dump(m); dump(l); dump(r);
			if (a[m] > s)r = m - 1;
			else if (a[m] < s)l = m + 1;
			else break;
		}
		cout << cnt << 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 (1){
		scanf("%d", &n);
		
		if (n == 0)break;
		
		for (i = 0; i < n; i++){
			scanf("%d", &x[i]);
		}
		
		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);
}

C++: #include <stdio.h>
int n, x, a[100];
int main() {
	while(scanf("%d", &n), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &x);
		int l = 0, r = n - 1, c = 0; bool flag = false;
		while(true) {
			int m = (l + r) / 2; c++;
			//printf("%d %d %d\n", l, r, m);
			if(a[m] == x) {
				printf("%d\n", c); flag = true; break;
			}
			if(r - l == 0) break;
			if(a[m] > x) r = m - 1;
			else l = m + 1;
		}
		if(!flag) printf("%d\n", c);
	}
}

C++: #include<stdio.h>
int dat[100];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)scanf("%d",dat+i);
		int count=0;
		int left=0;
		int right=a-1;
		int n;
		scanf("%d",&n);
		while(1){
			int M=(left+right)/2;
			count++;
			if(dat[M]==n)break;
			if(dat[M]>n){
				right=M-1;
			}
			if(dat[M]<n){
				left=M+1;
			}
			if(right<left)break;
		}
		printf("%d\n",count);
	}
}

C++: #include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int main(){
	int set[101],n,k,cnt,a,b;
	while(1){
	cin >> n;
	if(n==0)break;
	for(int i=0;i<n;i++){
		cin >> set[i];
	}

	cin >> k;
	cnt=0;
	n--;
	for(int i=0,j=n;i!=j;cnt++){
		a=(i+j)/2;
		if(set[a]==k) break;
		else if(set[a]<k) i=a+1;
		else j=a-1; 
	}
	cout << cnt+1;
}
}

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

using namespace std;

int s[100010],t[50010];
int n, q, ans = 0;

bool binary_search(int x) {
	int l = 0, r = n-1;
	ans = 0;
	while (r - l >= 0) {
		int m = (l + r) / 2;
		if (s[m] == x) {
			ans++;
			return true;
		}
		else if (s[m] > x) {
			r = m-1;
			ans++;
		}
		else if (s[m] < x) {
			l = m+1;
			ans++;
		}
	}
	
	return false;
}
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) {
			cin >> s[i];
		}
		cin >> t[0];
		binary_search(t[0]);
		for (int i = 0; i < n; i++) {
			s[i] = 0;
		}
			cout << ans << endl;
	}
	return 0;
}