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;

void bubble(int N, int data[]){
	int tmp=0;
	int cnt=0;
	int i=0, j=0;
	
	for(i=0;i<N;++i){
		cnt = 0;
		for(j=N-1;j>i;--j){
			if(data[j]<data[j-1]){
				tmp       = data[j-1];
				data[j-1] = data[j];
				data[j]   = tmp;
				cnt++;
			}
		}
		if(cnt==0) break;
	}
}

int BS(int key, int array[], int head, int tail, int count){
	count++;
	if(head >= tail){
		return count;
	}else{
		if(array[head + (tail-head)/2] == key){
			return count;
		}else{
			if(array[head + (tail-head)/2] > key){
				return BS(key, array, head, (tail-head)/2-1+head, count);
			}else{
				return BS(key, array, (tail-head)/2+1+head, tail, count);
			}	
		}
	}
}

int main() {
	int N=0;
	int data[100];
	int key=0;
	
	while(cin >> N, N!=0){
		for(int i=0; i<N; ++i){
			cin >> data[i];
		}
		cin >> key;
		
		bubble(N, data);
		
		cout << BS(key, data, 0, N, 0) << endl;
		
		for(int i=0;i<N;++i){
			data[i] = 0;
		}
	}
}

C++: #include <iostream>
#include <stdlib.h>

using namespace std;

int main(int argc, char **argv)
{
	int *a, n, t, l, h, c, p;
	
	while(1){
		cin >> n;
		if(n == 0){
			break;
		}
		a = (int *)calloc(n, sizeof(int));
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		cin >> t;
		l = c = 0;
		h = n-1;
		while(l <= h){
			p = (l + h)/2;
			c++;
			if(t == a[p]){
				break;
			} else if(t < a[p]){
				h = p - 1;
			} else {
				l = p + 1;
			}
		}
		cout << c << endl;
		
		free(a);
	}
	
	
	return 0;
}

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

int n[101];
int m;
int ans;
int N;

void func(int j,int k){
 ans++;
 if (n[(j+k)/2]==m||j>k) {
  return;
 }
 else {
  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 <cstdio>

int n,k;
int a[200];

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

C++: // clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return ~n & 1; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  int n;
  while (cin >> n, n) {
    vi a(n);
    cin >> a;
    int k;
    cin >> k;
    int up = n - 1, low = 0;
    int c = 0;
    forever {
      int mid = low + (up - low) / 2;
      c++;
      if (a[mid] == k || low == up) break;
      if (a[mid] > k) up = mid - 1;
      if (a[mid] < k) low = mid + 1;
      if (up < low) break;
    }
    cout << c << endl;
  }
}

C++: #include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

////////////////*My library*////////////////////////
#define rep_to(a,i,n) for(i=a;i<n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define rep_r(i,n) for(i=n-1;i>=0;i--)
#define debug_i(x) printf("x:%d\n",x)
#define debug_f(x) printf("x:%f\n",x)
#define debug_s(str) printf("str:%s\n",str)
#define debug_c(c) printf("c:%c\n",c)
#define s_i1(x) scanf("%d",&x)
#define s_i2(x,y) scanf("%d %d",&x,&y)
#define s_i3(x,y,z) scanf("%d %d %d",&x,&y,&z)
////////////////////////////////////////////////////
////////////////////////
/*prime()*/
/*primecount()*/
/*sort()*/
///////////////////////
int main()
{
	int i,j;
	int n,num[100000]={},key;

	while(1)
	{
		s_i1(n);
		if(n==0)break;
		rep(i,n)s_i1(num[i]);
		s_i1(key);

	/////????????¢?´¢//////////////////

		int min=0;
		int max=n-1;
		int mid=(min+max)/2;
		int count=1;
		while(min<max)
		{
			count++;
			mid=(min+max)/2;
			if(key==num[mid])break;
			else if(key>num[mid])min=mid+1;
			else if(key<num[mid])max=mid-1;
		}
	///////////////////////////////
	printf("%d\n",count+1);
	}
return 0;
}

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;
		while(1) {
			int mid = (hi+lo) / 2;
			cnt++;
			if(lo == hi || a[mid]==t) break;
			else if(a[mid]<t) lo = mid+1;
			else hi = mid;
		}
		cout << cnt << endl;
	}
	return 0;
}

C++: #define _CRT_SECURE_NO_WARNINGS

#include<fstream>
#include<iostream>
#include<string>
#include<iomanip>
#include<list>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

int main(){
	int n;
	while (cin >> n && n != 0) {
		int num[100] = { 0 };
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		int sea;
		cin >> sea;
		int ans = 0;
		int index = (n >> 1) - !(n & 1);
		int cnt = n;
		while (cnt > 0) {
			ans++;
			cnt = cnt >> 1;
			if (num[index] == sea) {
				break;
			}
			if (num[index] > sea) {
				index = index - ((cnt >> 1) + (cnt & 1));
			}
			else {
				index = index + ((cnt >> 1) + (cnt & 1));
			}
		}
		cout << ans << endl;
	}
	return 0;
}