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 <vector>

using namespace std;

void solve()
{
	int n;
	while(cin >> n, n)
	{
		vector<int> Vec(n);
		for(int i = 0; i < n; ++i)
		{
			cin >> Vec[i];
		}
		int target;
		cin >> target;
		int left = 0;
		int right = n - 1;
		int count = 1;
		while(target != Vec[(left + right) / 2] && right > left)
		{
			count++;
			if(target < Vec[(left + right) / 2])
			{
				right = (left + right) / 2 - 1;
			}
			else
			{
				left = (left + right) / 2 + 1;
			}
		}
		cout << count << endl;
	}
}

int main()
{
	solve();
	return(0);
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n;
	while(cin >> n , n){
		int need , ans = 0;
		vector<int> d(n);
		rep(i,n) cin >> d[i];
		
		cin >> need;
		int l = 0 , r = n-1;
		while( l < r ){
			ans++;
			int m = (l+r)/2;
			if(d[m] > need) r = m-1;
			else if(d[m] < need) l = m+1;
			else {break;}
		}
		cout << ans << endl;
	}
}

C++: #include<iostream>
using namespace std;
int a[100];
int main(){
	int n,key;
	while(true){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++)cin>>a[i];
		cin>>key;
		int ans=1;
		int left=0,right=n,mid;
		while(true){
			if(left>right)break;
			mid=(left+right)/2;
			if(a[mid]==key)break;
			if(a[mid]<key)left=mid+1;
			if(a[mid]>key)right=mid-1;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int main()
{
    int n,k,l,r,cnt,a[110];
    while(cin >> n,n!=0){
        for(int i=0;i<n;i++) cin >> a[i];
        cin >> k;
        l = 0;
        r = n-1;
        cnt = 0;
        while(l <= r){
            cnt++;
            int mid = (l+r)/2;
            if(k == a[mid]) break;
            if(k < a[mid]) r = mid-1;
            if(a[mid] < k) l = mid+1;
        }
        cout << cnt << endl;
    }
    return 0;
}

C++: /* {{{ Shinobu kawaii */
/*
  ______   __        _                  __                 
.' ____ \ [  |      (_)                [  |                
| (___ \_| | |--.   __   _ .--.   .--.  | |.--.   __   _   
 _.____`.  | .-. | [  | [ `.-. |/ .'`\ \| '/'`\ \[  | | |  
| \____) | | | | |  | |  | | | || \__. ||  \__/ | | \_/ |, 
 \______.'[___]|__][___][___||__]'.__.'[__;.__.'  '.__.'_/ 
                                                           
*/
/* }}} */

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

// #define int long long

/* cpp template {{{ */

/* short */
#define pb push_back
#define mp make_pair
#define print(x) cout << x << '\n'
#define Fi first
#define Se second

/* REPmacro */
#define REPS(i, a, n) for (int i = (a); i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = 1; i <= (n); i++)
#define DEPS(i, a, n) for (int i = (a); i >= n; i--)
#define DEP(i, n) for (int i = (n); i >= 0; i--)

/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;

/* const */
const int INF = 999999999;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

/* func */
inline bool is_uruu(int y) {return (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0));}
inline bool inside(int y, int x, int H, int W) {return (y >= 0 && x >= 0 && y < H && x < W);}

/* }}} */

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  for (int n; cin >> n, n;){
    vi a(n); REP(i, n) cin >> a[i];
    int ans; cin >> ans;
    int mid, l = 0, r = n - 1;
    int cnt = 0;
    do {
      cnt++;
      mid = (l + r) / 2;
      if (a[mid] == ans){
        break;
      }
      if (a[mid] <= ans){
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    } while (r - l >= 0);
    print(cnt);
  }

  return (0);
}

C++: #include<stdio.h>

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

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

vector<int> data;
int bsearch(int n) {
    int count = 0;
    int l = 0, r = data.size();
    int mid = 0, prev_mid;
    while (true) {
        prev_mid = mid;
        mid = (l + r) / 2;
        if (prev_mid == mid) break;
        count++;
        if (data[mid] < n) {
            l = mid;
        } else if (data[mid] == n) {
            return count;
        } else {
            r = mid;
        }
    }
    return count;
}

int main() {
    int n;
    while (cin >> n) {
        data.clear();
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            int t; cin >> t;
            data.push_back(t);
        }
        int find_n; cin >> find_n;
        cout << bsearch(find_n) << endl;
    }
    return 0;
}

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

vector<int> arr;
int n;

int main(void){
  while(cin >> n, n){
    int num;
    arr.clear();
    for(int i = 0; i < n; i++){
      cin >> num;
      arr.push_back(num);
    }
    int search, cnt = 0;
    cin >> search;
    int lb = -1, ub = n;
    while(ub - lb > 1){
      int mid = (lb + ub) / 2;
      cnt++;
      if(arr[mid] >= search){
        ub = mid;
      }else{
        lb = mid;
      }
    }
    cout << cnt << endl;
  }
  return 0;
}

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(r>=l)break;
        if(T[(r+l)/2]==x)return ans;
        if(T[(r+l)/2]>x)l=(r+l)/2-1;
        else if(T[(r+l)/2]<x)r=(r+l)/2+1;
if(r>l) break;
    }
    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<iostream>

using namespace std;



int main(){
	int num[101],r[2];
	int kazu, target, t;
	int i;

	while (1){
		t = 0;
		cin >> kazu;

		if (kazu == 0){
			break;
		}

		for (i = 0; i < kazu; i++){
			cin >> num[i];
		}

		cin >> target;


		r[0] = 0;
		r[1] = (kazu - 1);
		t = 0;
		
		while (1){
			t++;
			if (num[(r[0] + r[1]) / 2] == target){
				break;
			}else if (r[0] == r[1]){
				break;
			}else if(num[(r[0] + r[1]) / 2] < target){
				r[0] = (r[0] + r[1]) / 2 + 1;
			}else{
				r[1] = (r[0] + r[1]) / 2 - 1;
			}
								
		}


		cout << t << endl;
	}

}