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;
typedef long long int lld;
typedef pair<int,string> P;
#define INF (1<<20)

int main(){
  int n;
  int num[1111];
  while(cin >> n){
    for(int i=0;i<n;i++){
      cin >> num[i];
    }
    sort(num,num+n);
    int tar; cin >> tar;
    int cnt = 0;
    int left = 0;
    int right = n-1;
    while(left < right){
      int mid = (left+right)/2;
      cnt++;
      if(mid == tar) break;
      else if(mid > tar) right = mid - 1;
      else left = mid + 1;
    }
    cout << cnt+1 << endl;
  }
}

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 (v[mid] == search) {
                break;
            } else if (search < v[mid]) {
                h = mid-1;
            } else {
                l = mid+1;
            }
        }
        cout << res << endl;
    }
    return 0;
}

C++: #include <iostream>

using namespace std;

#define MAX_N 101

int a[MAX_N];

int main() {
    int n, f;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> f;
        int count = 0;
        int r = n-1, l = 0;
        int mid;
        while (true) {
            mid = (r+l) / 2;
            count++;
            if (a[mid] == f) {
                 break;
            }
            if (r == l) break;
            if (r < l) break;
            if (a[mid] < f) {
                l = mid+1;
            }
            if (a[mid] > f) {
                r = mid-1;
            } 
        }
        cout << count << endl;
    }
    return 0;
}

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

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

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

int main() {
    int N;
    while (cin >> N, N) {
        vector<int> v(N);
        for (auto& i : v) cin >> i;

        int x;
        cin >> x;
        int l = 0, r = N - 1;

        int count = 0;
        while (true) {
            int m = (r + l) / 2;
            count++;
            if (v[m] == x) break;
            if (l >= r) break;

            if (v[m] < x) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        cout << count << 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,kawa[2]={0,n-1};
        for(int i=1;kawa[1]>=kawa[0];i++){
            serch=(kawa[0]+kawa[1])/2;
            if(num[serch]==ans){
                cout<<i<<endl;
                break;
            }
            if(num[serch]>ans)kawa[1]=serch-1;
            else kawa[0]=serch+1;
            if(kawa[0]>kawa[1])cout<<i<<endl;
        }
    }
}

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>
#include<cstdio>
#include<cstdlib>
#include<stdexcept>
#include<cmath>
#include<memory>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<deque>
#include<sstream>
#include<iomanip>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<map>
#include<set>
#include<list>
#include<cassert>
#include<deque>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<27
#define all(n) n.begin(),n.end()
#define insert(a,b,c,d) PP(P(a,b),P(c,d))
#define F first
#define S second
#define pb push_back
#define pf push_front
#define LIM 100000
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef long long ll;
typedef unsigned long long ull;

int main(){

  while(true){
    int n;
    cin >> n;
    if(n == 0)break;
    vector<int> vec;
    rep(i,n){
      int in; cin >> in;
      vec.pb(in);
    }
    int key,cnt = 0;
    cin >> key;
    int l,r,m;
    l = 0,r = n-1;
    while(l < r){
      m = (l+r)/2;
      cnt++;
      if(vec[m] == key)break;
      if(vec[m] > key)r = m;
      else l = m+1;
    }
    cout << cnt << 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){
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start > end) break;
    if(data[now] > wanted) end = now;
    else start=now+1;
  }
}

int main(){
  while(cin >> n && n){
    ans = 0;
    for(int i = 0; i < n; i++) cin >> data[i];
    cin >> wanted;
    solve();
    cout << ans << endl;
  }
  return 0;
}

C++: #include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int n;
	cin >> n;
	vector<int> a(n);
	if(n == 0) break;
	REP(i,n) cin >> a[i];
	int num;
	cin >> num;
	int l,m,h,ans;
	h = n;
	l = 0;
	m = (h+l)/2;
	ans = 0;
	while(h-l > 1){
	    if(a[m] > num){
		h = m;
	    }else if (a[m] < num){
		l = m;
	    }else{
		ans++;
		break;
	    }
	    m = (h+l)/2;
	    ans++;
	}
	if(a[m] != num){
	    ans++;
	}
	cout << ans << endl;
    }
    return 0;
}