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

int n, target;

int binserch(int* s, int* e) {
	if (s == e) return 0;
	int* c = s + (e - s - 1) / 2;
	if (*c < target) {
		return binserch(c + 1, e) + 1;
	}
	else if (target < *c) {
		return binserch(s, c) + 1;
	}
	else {
		return 1;
	}
}

int main() {
	while (cin >> n, n) {
		int a[n];
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		cin >> target;
		cout << binserch(a, a + n) << 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 = 1;
		while (1){
			
			i = (max + min) / 2;
			if (x[i] < obj){
				min = i + 1;
			}else if (x[i] > obj){
				max = i - 1;
			}else{
				break;
			}
			
			if (max == min){
				ans++;
				break;
			}
			ans++;
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}

C++: #include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n;
    while(cin >> n, n){
        int data[105];
        rep(i,n){
            cin >> data[i];
        }
        int ans = 0, search;
        cin >> search;
        int start = 0, end = n - 1;
        int p;
        while(end >= start){
            p = (end + start) / 2;
            ans++;
            if(search > data[p])
                start = p + 1;
            else if(search < data[p])
                end = p - 1;
            else
                break;
        }
        cout << ans << endl;
    }
}

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<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;

int main(){
    int n,a[101],X;
    while(1){
    cin >> n;
    if(n==0)break;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    cin >> X;
    int high=n-1,low=0,cnt=0;
    while(high>=low){
        cnt++;
        int center=(low+high)/2;
        if(a[center]==X) break;
        else if(a[center]<X) low=center+1;
        else high=center-1;
    }
    cout << cnt << endl;
    }
}

C++: #include <iostream>
#include <math.h>
using namespace std;
int main(){
    int a, b, times;
    int i1, tyuusinn, yousosuu, yousosuu2;
    while(1){
    cin >> a;
    if(a==0){break;}
    i1=0;
        times=0;
    int w[a];
    while(1){
        cin >> b;
        w[i1]=b;
        i1++;
        if(i1==a)break;
    }
    sort(w, w+a);
    cin >> b;
    yousosuu=a;
    
    tyuusinn=(yousosuu-1)/2;
        while(1){
    times++;
    yousosuu2=(yousosuu-1)/2;
    if(w[tyuusinn]==b){break;}
    else if(w[tyuusinn]>b){
        tyuusinn=tyuusinn-yousosuu2+(yousosuu2-1)/2;
        yousosuu=yousosuu2;
    }
    else{
        if(yousosuu%2==0){
            tyuusinn=tyuusinn+(yousosuu2+1)/2;
            yousosuu=yousosuu2+1;
        }
        else{
            tyuusinn=tyuusinn+(yousosuu2+1)/2+1;
            yousosuu=yousosuu2;
        }
    }
            if(yousosuu==0){break;}
        }
        
    cout << times << endl;
}
    return 0;
}

C++: #include <cstdio>
#include <cmath>
int n, x;
int a[100];
int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<n; i++) scanf("%d",&a[i]);
        scanf("%d", &x);
        int lb=0, ub=n-1, res=0;
        while (ub>=lb) {
            res++;
            int mid=floor((lb+ub)/2);
            if (a[mid]<x) {
                lb=mid+1;
            } else if (a[mid]>x) {
                ub=mid-1;
            } else {
                break;
            }
        }
        printf("%d\n",res);
    }
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,s;
  while(cin >> n&&n){
    vary(int,v,n+5,0);
    rep(i,n+1){
      cin >> v[i];
    }
    int lb = 0,ub = n-1;
    int ans = 0;
//     debug(v[n]);
    while(1){
      int mid = (lb+ub)/2;
      ++ans;
      if(mid == ub || v[n] == v[mid]){
        break;
      }
      if(v[mid] < v[n]){
        lb = mid+1;
      }
      else{
        ub = mid-1;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

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

using namespace std;

int main(){

	int n;
	while(cin>>n&&n!=0){
		vector<int> nums;
		int t;
		for(int i = 0; i < n; i++){
			cin>>t;
			nums.push_back(t);
		}
		int s;
		cin>>s;
		int ub=n-1;
		int lb=0;
		int cnt=0;
		while(1){
			if(lb<0||ub<0)
				break;
			int mid=ub+lb;
			mid/=2;
			cnt++;
			if(nums[mid]==s||ub==lb){
				break;
			}
			else if(nums[mid]>s){
				ub=mid-1;
			}
			else if(nums[mid]<s){
				lb=mid+1;
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}