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

int search2(int,int,int,int[],int);

int main() {
	// your code goes here
	int n,low,high,mid,number,ans;
	int num[110]={};
	for(;;){
	cin>>n;
	if(n==0){
		break;
	}
	for(int i=0;i<110;i++){
		num[i]=0;
	}
	for(int i=0;i<n;i++){
		cin>>num[i];
	}
	cin>>number;
	sort(num,num+n);
	int ans=0;
	ans = search2(0,n,number,num,ans);
	cout<<ans<<endl;
	}
	return 0;
}

int search2(int low,int high,int number,int num[],int ans){
	ans++;
	int mid=(low+high)/2;
	if(num[mid]==number||low==high||low>high){
		return ans;
	}else if(num[mid]<number){
		low=mid+1;
		search2(low,high,number,num,ans);
	}else if(num[mid]>number){
		high=mid-1;
		search2(low,high,number,num,ans);
	}
	
	
}

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;

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

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 {ans--;break;}
		}
		cout << ans+1 << endl;
	}
}

C++: #include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
	int n;
	while (cin >> n&&n != 0) {
		int a[100], k = 0, s = 0, e = n - 1, sum = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		cin >> k;
		while (s - e!=1) {
			int b = floor((s + e) / 2);
			if (a[b] < k) {
				s = b+1;
				sum++;
			}
			else if (a[b] > k) {
				e = b-1;
				sum++;
			}
			else {
				sum++;
				break;
			}
		}
		cout << sum << endl;
	}
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
#include <cmath>
#include <cstdio>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()

using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int num[101];
int main(void){
	int n;
	while(cin >> n, n){
		rep(i, n) cin >> num[i];
		int x;
		cin >> x;

		int lb = 0, ub = n-1;
		int ans = 0;
		while(1){
			int mid = (ub+lb)/2;
			ans++;
			if(ub <= lb) break;
			if(num[mid] == x) break;
			if(num[mid] < x) lb = mid+1;
			else ub = mid-1;
		}

		cout << ans << endl;
	}

    return 0;
}

C++: //43
#include<iostream>

using namespace std;

int main(){
  for(int n;cin>>n,n;){
    int a[100];
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    int ans=0;
    int f=0,l=n-1;
    int g;
    cin>>g;
    for(;;){
      int m=f+(l-f)/2;
      if(l-f<0){
	break;
      }else{
	ans++;
	if(a[m]==g){
	  break;
	}else if(a[m]>g){
	  l=m-1;
	}else{
	  f=m+1;
	}
      }
    }
    cout<<ans<<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) end = now-1;
    else start=now+1;
    if(data[now] == wanted || start >= end) break;
  }
}

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

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

int a[1000],n,cnt,L,R,M,p;

int main(){
	while(true){
		cin>>n;
		if(n==0){break;}
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		cin>>p;
		L=0;R=n-1;cnt=0;
		while(R-L>=1){
			cnt++;
			M=(R+L)/2;
			if(p==a[M]){break;}
			if(p>a[M]){L=M+1;}
			if(p<a[M]){R=M-1;}
		}
		cout<<cnt+1<<endl;
	}
}

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

int main(void){
	int i,n,x[104],search;
	int l,r,c;
	int count;

	while(cin>>n && n){
		for(i=0;i<n;i++) cin>>x[i];
		cin>>search;

		for(count=1,l=0,r=n-1,c=(l+r)/2;l!=r;c=(l+r)/2,count++){
			if(search < x[c]) r = c - 1;
			else if(search > x[c]) l = c + 1;
			else break;
		}
		cout<<count<<endl;
	}

	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
using namespace std;

int main()
{
	int a;
	while (cin >> a, a) {
		int b[100];
		for (int c = 0; c < a; c++)cin >> b[c];
		int d;
		cin >> d;
		int MIN = 0, MAX = a - 1, sum = 1;
		while (1) {
			int e = (MIN + MAX) / 2;
			if (MIN==MAX)break;
			if (b[e] < d)MIN = e+1;
			else if (b[e] > d)MAX = e-1;
			else break;
			sum++;
		}
		cout << sum << endl;
	}
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  int n;
  while(cin>>n,n){
    vector<int>in(n);
    rep(i,n)cin>>in[i];
    int t=0,l=n-1;
    int co=0;
    int out;
    cin>>out;
    while(t<=l){
      int tmp=(t+l)/2;
      //tmp=in[tmp];
      co++;
      if(in[tmp]==out)break;
      if(in[tmp]<out)t=tmp+1;
      if(in[tmp]>out)l=tmp-1;
    }
    cout<<co<<endl;
  }

}

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

int n, comparison;
int num[101];

void binarysearch(int v){
  int l = 0;
  int r = n-1;
  int x;
 
  while(l <= r){
    x = (l+r)/2;
    comparison++;
    if(num[x] < v) l = x+1;
    else if(num[x] > v) r = x-1;
    else break;
  }
}

int main(){
  int search_value;
  
  while(cin >> n, n){
    comparison = 0;
    for(int i = 0 ; i < n ; i++){
      cin >> num[i];
    }
    cin >> search_value;
    
    binarysearch(search_value);
    
    cout << comparison << endl;
  }
  return 0;
}