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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int main() {
	int n;
	int num[110];
	while(n=in()){
		int i;
		for(i=0;i<n;i++){
			cin>>num[i];
		}
		int g=in();
		int a=0,b=n-1;
		int res=1;
		while(num[(a+b)/2]!=g){
//cout<<a<<" "<<b<<endl;
			if(num[(a+b)/2]>g)b=(a+b)/2-1;
			else a=(a+b)/2+1;
			res++;
			if(a>=b)break;
		}
		cout<<res<<endl;
	}
	return 0;
}

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

vector<int> arr;
int n;

int main(void){
  while(true){
    cin >> n;
    if(!n) break;
    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 <cstdio>
using namespace std;

int main()
{
	int array[1000];
	int n;
	
	while (scanf("%d", &n), n){
		for (int i = 0; i < n; i++){
			scanf("%d", &array[i]);
		}
		
		int q;
		scanf("%d", &q);
		
		int l = 0;
		int r = n - 1;
		int cnt = 0;
		while (1){
			int m = (l + r) / 2;
			
			cnt++;
			
			if (q == array[m]){
				break;
			}
			
			else if (l == r){
				break;
			}
			
			else if (q < array[m]){
				r = m - 1;
				if (r < l){
					break;
				}
			}
			
			else if (q > array[m]){
				l = m + 1;
				if (l > r){
					break;
				}
			}
		}
		
		printf("%d\n", cnt);
	}
	
	return 0;
}

C++: #include<stdio.h>
int main()
{
	int n,i,a[100],l,m,r,x,c;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;++i)scanf("%d",&a[i]);
		scanf("%d",&x);
		for(c=l=0,r=n;l<r;)
		{
			++c;
			m=(l+r)/2;
			if(a[m]==x)break;
			else if(a[m]<x) l=m+1;
			else r=m;
		}
		printf("%d\n",c);
	}
	return 0;
}

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

int main(){
  int n;
  int t[102];

  while(cin >> n, n){
    for(int i = 0; i < n; i++){
      cin >> t[i];
    }

    int x;
    cin >> x;

    int lo = 0;
    int hi = n - 1;
    int cnt = 0;

    while(lo <= hi){
      cnt++;
      int med = (lo + hi) / 2;

      if(t[med] == x) break;
      if(t[med] > x){
	hi = med - 1;
      }
      else{
	lo = med + 1;
      }
    }

    cout << cnt << endl;
  }
}

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

C++: #include <cstdio>
#include <cmath>
#define buf 1000001
using namespace std;
int cnt,b[buf]={0};
void binary_search(int d,int a);

int main(void){
  int i,j,a,n;
  char str[200];

  for( ; ; ){
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&a);
    if(a==0) return 0;
    for(i=0;i<a;i++){
      fgets(str,sizeof(str),stdin);
      sscanf(str,"%d",&n);
      b[i]=n;
    }
    cnt=0;
    fgets(str,sizeof(str),stdin);
    sscanf(str,"%d",&n);
    binary_search(n,a);
    printf("%d\n",cnt);
  }
  return 0;
}

void binary_search(int n,int a){
  int left,right,mid;
  double tmp;
  left = 0; right = a-1;
  while(left < right){
    tmp = floor((left + right)/2);
    mid=tmp;
    cnt++;
    if(b[mid] == n)
      break;
    else if(n < b[mid])
      right = mid;
    else if(n > b[mid])
      left = mid+1;
  }
}

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-yousosuu+yousosuu2/2;
        yousosuu=yousosuu2+1;
    }
    else{
        if(yousosuu%2==0){
            tyuusinn=tyuusinn+yousosuu2/2-1;
            yousosuu=yousosuu2+1;
        }
        else{
            tyuusinn=tyuusinn+(yousosuu2+1)/2+1;
            yousosuu=yousosuu2;
        }
    }
            if(yousosuu==0){break;}
        }
        
    cout << times << endl;
}
    return 0;
}

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

int main( void )
{
	int n;
	while ( cin >> n && n )
	{
		vector <int> values;
		for ( int i = 0; i < n; i++ )
		{
			int v;
			cin >> v;
			values.push_back( v );
		}

		sort( values.begin(), values.end() );

		int s;
		cin >> s;

		int left  = 0;
		int right = n - 1;
		int answer = 0;
		while ( left <= right )
		{
			int m = ( left + right ) / 2;
			if ( s == values[m] )
			{
				answer++;
				break;
			}
			else if ( s > values[m] )
			{
				left = m + 1;
				answer++;
			}
			else if ( s < values[m] )
			{
				right = m - 1;
				answer++;
			}
		}

		cout << answer << 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||ub>=n||lb>=n||ub<lb)
				break;
			cnt++;
			int mid=ub+lb;
			mid/=2;
			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;
}