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>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int main(){
  int n;
  while(cin>>n, n){
    vector<int> v(n);
    REP(i,n) cin>>v[i];
    
    int cnt = 0;
    int low = 0, high = n-1;
    int s; cin>>s;
    while(true){
      int mid = (low+high)/2;
      //cout << "mid=" << mid << endl;
      cnt++;
      if(v[mid] == s) break;
      if(low >= high) break;
      if(v[mid] > s){
	high = mid-1;
      }else{
	low  = mid+1; 
      }
    }
    cout << cnt << endl;
  }
  return 0;
}

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

int T[100010];
int find(int m,int x){
	int r=0,l=m,ans=0;
	while(1){
		ans++;
		if(T[(r+l)/2]==x)return ans;
		else if(r>l)break;
		if(T[(r+l)/2]>x)l=(r+l)/2-1;
		else if(T[(r+l)/2]<x)r=(r+l)/2+1;
	}
	return ans;
}
int main(){
	int n,k,num,ans;
	while(1){
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>T[i];
		}
		cin>>k;
		ans=find(n,k);
		cout<<ans<<endl;
	}
	return 0;
}

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

using namespace std;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		vector<int> data(n);
		int left = 0;
		int right = n-1;
		for (int i = 0; i < n; i++) {
			cin >> data[i];
		}
		int counter = 0;
		int tansa;
		cin >> tansa;
		while (true) {
			int half = (left+right) / 2;
			counter++;
			if (data[half] == tansa) {
				break;
			} else if (left == right) {
				break;
			} else if (data[half] < tansa) {
				left = half+1;
			} else {
				right = half-1;
			}
		}
		cout << counter << endl;
	}
	return 0;
}

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-1){
		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 <stdio.h>
#include <stack>
#include <math.h>

using namespace std;

struct Info{
	int id,sum;
};

int main(){

   int n,k,table[100],left,right,count,m;

   while(true){
	   scanf("%d",&n);
	   if(n == 0)break;

	   for(int i=0; i < n; i++)scanf("%d",&table[i]);

	   scanf("%d",&k);

	   count = 0;
	   left = 0,right = n;
	   m = (left+right)/2;
	   while(true){
		   count++;
		   if(table[m] == k)break;
		   else{
			   if(right-left==1){
				   if(table[right] < n && table[right] == k)count++;
				   break;
			   }
			   if(table[m] < k){
				   left = m;
				   m = (left+right)/2;
			   }else{
				   right = m;
				   m = (left+right)/2;
			   }
		   }
	   }

	   printf("%d\n",count);

   }

    return 0;
}

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


int main(){
    int n, search;
    while (cin >> n && n){
	int inp[101];
	for (int i = 0; i < n; i++) cin >> inp[i];
	cin >> search;

	int *s = inp, *e = inp + n - 1, *p = inp + (n-1)/2;
	int ans = 0;
	int b = 0;
	while (1){
	    ans++;
	    cout << *s << " " << *p << " " << *e << endl;
	    if (p == s && p == e) break;
	    if (*p == search) break;
	    else if (*p > search){
		e = p-1;
		p = s + (e - s)/2;
	    }
	    else if (*p < search){
		s = p+1;
		p = s + (e - s)/2;
	    }
	}

	cout << ans << endl;
    }
}

C++: #include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;
 
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
 
typedef long long ll;

const int MAX_N = 101;
int N, k;
int a[MAX_N];

void solve() {
	sort(a, a+N);
	int c = 0;
	int l = 0;
	int r = N-1;
	do {
		c++;
		int mid = (l + r) / 2;
		if(a[mid] == k) {
			break;
		}
		else if(a[mid] < k) {
			l = mid+1;
		}
		else if(a[mid] > k) {
			r = mid-1;
		}
	} while(l <= r);
	printf("%d\n", c);
}

int main() {
	while(scanf("%d", &N), N) {
		rep(i,N) scanf("%d", &a[i]);
		scanf("%d", &k);
		solve();
	}
}

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 , m;
		do{
			ans++;
			m = (l+r)/2;
			if(d[m] > need) r = m-1;
			else if(d[m] < need) l = m+1;
		}while(need != d[m] && m != r && m != l);
		cout << ans << endl;
	}
}

C++: #define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

int main(){
	int n;
	while(~scanf("%d",&n)){
		if(n==0) break;

		int* a = new int[n];
		for(int i=0;i<n;i++){
			scanf("%d",a+i);
		}

		int dst;
		scanf("%d",&dst);
		
		int lb = 0;
		int ub = n-1;

		int res=-1;
		for(int i=2;i<=50;i++){
			int md = (lb+ub)/2;
			if(dst == a[md]){
				res = i;
				break;
			}
			else if(dst < a[md]) ub = md;
			else lb = md;
			
			if(ub-lb==1){
				res = i;
				break;
			}
		}
		printf("%d\n",res);
		delete[] a;
	}
}

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

int main(){
    while(1){
        int n;
        cin >> n;

        if(n == 0)  break;

        int A[n];
        for(int i = 0; i < n; i++)  cin >> A[i];

        int x;
        cin >> x;
        int ans = 0;
        int r = n-1, l = 0;

        while(l < r){
            ans++;
            int mid = (r+l)/2;
            if(A[mid] == x) break;
            else if(A[mid] < x) l = mid+1;
            else if(A[mid] > x) r = mid-1;
        }

        cout << ans+1 << endl;
    }
    return 0;
}

C++: #include<iostream>

using namespace std;



int main(){
	int num[101],r,l,c;
	int kazu, target, t;
	int i;

	while (1){
		t = 0;
		cin >> kazu;

		if (kazu == 0){
			break;
		}

		for (i = 0; i < kazu; i++){
			cin >> num[i];
		}

		cin >> target;


		l = 0;
		r = (kazu - 1);
		t = 0;
		while (1){
			c = (l + r) / 2;
			t++;
			if (num[c] == target){
				break;
			}else if (r<=l){
				break;
			}else if(num[c] < target){
				l = c + 1;
			}else{
				r = c - 1;
			}
								
		}


		cout << t << endl;
	}

}