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 <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){
    ll tar;
    vary(int,v,n,0);
    rep(i,n){
      cin >> v[i];
    }
    cin >> tar;
    int lb = 0,ub = n-1;
    int ans = 0;
    while(1){
      int mid = (lb+ub)/2;
      ++ans;
      if(lb >= ub){
        break;
      }
      if( tar == v[mid]) break;
      if(v[mid] < tar){
        lb = mid+1;
      }
      else{
        ub = mid-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){
    if(start > end) break;
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted) break;
    if(data[now] > wanted) end = now-1;
    else start=now+1;
  }
}

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

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

int main(){
	int *data, n, key, count, p, l, c;
	while(true){
		std::cin >> n;
		if(n==0)
			return 0;
		data = new int[n];
		for(int i=0; i<n; i++)
			std::cin >> data[i];
		std::sort(data, data+n);
		std::cin >> key;
		p=0, l=n-1,count = 1;
		while(true){
			c = (p+l)/2;
			if((p+l)%2 != 0)
				c = (p+l-1)/2;
			if(data[c] == key && p==l)
				break;
			if(p==l){
				count++;
				break;
			}
			if(data[c] > key)
				p = c+1;
			else
				l = c-1;
			count++;
		}
		std::cout << count << std::endl;
	}
}

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

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

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

int main() {
	int n;
	while(cin >> n, n) {
		vector<int> v;
		int f;
		for(int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp; v.push_back(tmp);
		}
		cin >> f;

		int l, r;
		l = 0; r = v.size() - 1;
		int ans = 0;
		while(l <= r) {
			int m;
			m = (l + r) / 2;
			ans++;
			if(v[m] == m)
				break;
			else if(v[m] < f)
				l = m + 1;
			else
				r = m - 1;
		}

		cout << ans << endl;
	}
}

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

using namespace std;

int binarySerch( const vector<int>& data, int target )
{
	int low, high;
	int answer = 0;
	low = 0;
	high = data.size() - 1;

	while( low <= high ){
		int ix = ( low + high ) / 2;
		answer++;
		
		if( data[ix] > target ){
			high = ix - 1;
		}else if( data[ix] < target ){
			low = ix + 1;
		} else {
			return answer;
		}
	}

	return answer;
}

int main(int argc, char const* argv[])
{
	int n;
	vector<int> data;
	int target;

	while( cin >> n && n != 0 ){
		data.clear();
		for( int i = 0;i < n;i++ ){
			int input;
			cin >> input;
			data.push_back( input );
		}
		cin >> target;

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

		cout << binarySerch( data, target ) << endl;
	}
	return 0;

}

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

using namespace std;

int main(void){
	int n;
	while(cin >> n && n){
		vector<int> v(n);
		int l=0,r=n-1,m,k,ans=0;;
		for(int i=0;i<n;i++){
			cin >> v[i];
		}
		cin >> k;
		while(l<=r){
			ans++;
			m = (r+l)/2;
			if(v[m] == k) break;
			if(v[m] < k){
				l = m+1;
			}else{
				r = m-1;
			}
		}
		cout << ans << endl;
	}
}

C++: #include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef pair<int,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
	int N;
	while(scanf("%d",&N),N){
		int array[128];
		rep(i,N){
			scanf("%d",&array[i]);
		}
		int M;
		scanf("%d",&M);
		int l = 0;
		int r = N;
		int cnt = 1;
		while(l+1 != r){
			int med = (l+r)/2;
			if(array[med] == M)break;
			if(array[med] > M)r = med;
			else l = med;
			cnt++;
		}
		printf("%d\n",cnt);
	}
    return 0;
}

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=0;
		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);
	}
return 0;
}