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<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--;
	a=n/2;
	for(int i=0,j=n;i<=j&&set[a]!=k;cnt++){
		a=(i+j)/2;
		if(set[a]<k) i=a+1;
		else j=a-1; 
	}
	cout << cnt << endl;
}
}

C++: #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n;
  while(1){
    cin>>n;
    if(n==0)break;
    vi a(n);
    rep(i,n)
      cin>>a[i];
    int k;
    cin>>k;
    int right=n-1,left=0;
    rep(i,n){
      int c=(right+left)/2;
      if(a[c]==k)break;
      if(a[c]<k)
        left=c+1;
      else
        right=c-1;
      if(right==left)break;
    }
  cout<<i+1<<endl;
  }
}

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

using namespace std;


int main() {

  int n;
  vector<int> data;
  int key;

  vector<int> next;
  int l,h,m;
  int count;

  int temp;


  while(cin >> n) {

    if(n==0) break;

    data.clear();

    for(int i=0;i<n;i++) {

      int tmp;

      cin >> tmp;

      data.push_back(tmp);

    }

    //for(int i=0;i<n;i++) cout << data[i] << " ";

    cin >> key;

    count=0;

    l=0;

    h=n-1;

    while(l<=h) {

      count++;

      m=(l+h)/2;

      if(key==data[m]) break;

      else if(key<data[m]) h=m-1;

      else l=m+1;

    }

    cout << count << endl;

  }

  return 0;

}

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<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;
    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<bits/stdc++.h>
using namespace std;

int main()
{
  int n;
  while( cin >> n, n ) {
    int target;
    int cnt = 1;
    int l = 0, r = n-1, m;
    int data[100001];
   
    for(int i=0; i<n; i++) cin >> data[i];
    cin >> target;
    
   

    while( l <= r ) {
      m = (l+r) / 2;
      if( data[m] == target ) break;
      if( target > data[m] ) l = m+1;
      else r = m-1;
      cnt++;
    }

    cout << cnt << endl;
  }

}

C++: #include <iostream>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
int main(){
	int n, a[110], t;
	while(cin >> n, n) {
		rep(i,n) {
			cin >> a[i];
		}
		cin >> t;
		int lo = 0, hi = n-1, cnt = 0, mid = -1;
		while(1) {
			if(mid == (hi+lo)/2) break;
			mid = (hi+lo) / 2;
			cnt++;
			if(a[mid]==t) break;
			else if(a[mid]<t) lo = mid+1;
			else hi = mid;
		}
		cout << cnt << endl;
	}
	return 0;
}

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

int main(){
    while(1){
        int n;
        cin >> n;

        if(n == 0)  break;

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

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

        while(l <= r){
            ans++;
            int mid = (r+l)/2;
            if(A[mid] == x || l > r) break;
            else if(A[mid] < x) l = mid+1;
            else if(A[mid] > x) r = mid-1;
        }

        cout << ans << endl;
    }
    return 0;
}

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

int main(void){
    int n;
    while(cin >> n, n){
        int data[10000];
        int need;
        for(int i=0; i < n; i++)
            cin >> data[i];
        cin >> need;
        if(n == 1){
            cout << 0 << endl;
            continue;
        }
        

        int before = 0, after = n-1;
        int cnt = 0;
        while(1){
            int mid = (after + before) / 2;
            cnt++;
            if(need == data[mid])
                break;
            if(before >= after)
                break;
            if(data[mid] > need)
                after = mid-1;
            else
                before = mid+1;
        }
        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-1,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;
    }
    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;
}