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 a[200];
int n;

int search(int i){
  int count = 0;
  int lix = 0,rix = n - 1;
  while(lix <= rix){
    //cout << lix << rix << endl;
    int med = (lix + rix)/2;

    count++;
    if(a[med] == i)return count;

    if(a[med] < i){
      lix = med + 1;
      continue;
    }

    if(a[med] > i){
      rix = med - 1;
      continue;
    }
  }
  return count;
}

int main(){

  while(true){
    cin >> n;
    if(n == 0)break;
    for(int i = 0;i < n;i++){
      cin >> a[i];
    }
      
    int i;
    cin >> i;
    cout << search(i) << endl; 
  }
}

C++: #include <cstdio>

int main(){
  int n,key;

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

    scanf("%d" ,&key);

    int lb = 0,ub = n-1,cnt = 0;
    while(ub - lb >= 0){
      int mid = (lb + ub) / 2;
      cnt++;

      if(key == a[mid]){
	break;
      }

      if(key < a[mid]){
	ub = mid - 1;
      }else{
	lb = mid + 1;
      }
    }   
    printf("%d\n" ,cnt);
  }

  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){
		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>
int n, a[100], t;
int main() {
	while(true) {
		scanf("%d", &n);
		if(n == 0) break;
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		scanf("%d", &t);
		int c = 0;
		int l = 0;
		int r = n - 1;
		while(true) {
			int m = (l + r) / 2; c++;
			if(a[m] == t) break;
			if(a[m] < t) {
				l = m + 1;
			}
			else {
				r = m - 1;
			}
		}
		printf("%d\n", c);
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int a[114514];
int n, key;
int binary_search(int sum, int l, int r) {
	int m = (l + r) / 2;
	sum++;
	if (a[m] == key)return sum;
	else if (l == r&&a[m] != key)return sum;
	else if (m > key)return binary_search(sum, 0, m - 1);
	else return binary_search(sum, m + 1, r);
}
int main() {
	while (cin >> n) {
		if (!n)return 0;
		for (int i = 0; i < n; i++)cin >> a[i];
		cin >> key;
		cout << binary_search(0, 0, n - 1) << 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);
	}
return 0;
}

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

#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int n;
    int a[1000];
    while(cin>>n && n){
        int cnt=0;
        rep(i,n)cin>>a[i];
        int f;cin>>f;
        int l=0, r=n-1;
        // [l,r]
        while(1){
            // cout << l << " " << r << endl;
            int m=(l+r)/2;
            cnt++;
            if(a[m]==f){}
            if(a[m]<f){
                l=m+1;
            }else{
                r=m-1;
            }
            if(l==r) break;
        }
        cout << cnt+1 << endl;
    }
}

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

int a[110];
int n, k;

//a[0], a[1], a[2]. ... , a[n - 1]?????????x?????????????????????????????????
int binary_search(int x){
    int res = 0;
	int l = 0, r = n;
	//[l, r)???????????????????????????????????§??°?????????
	while(r - l >= 1){
		int m = (l + r) / 2;
        res++;
		if(a[m] == x) return res; //x??????????????£?????´???
		else if(a[m] > x) r = m;
		else if(a[m] < x) l = m + 1;
	}
	//x???????????????????????£?????´???
	return res + 1;
}

int main(){
    while(cin >> n, n){
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        cin >> k;
        sort(a, a + n);
        cout << binary_search(k) << endl;
    }
}

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

using namespace std;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		vector<long long 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 (left == right) {
				break;
			}
			if (data[half] == tansa) {
				break;
			} else if (data[half] < tansa) {
				left = half+1;
			} else {
				right = half-1;
			}
		}
		cout << counter << endl;
	}
	return 0;
}

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

int find( int* a, int s, int e, int d )
{
	int m = ( s + e ) / 2;
	int r = 0;
	if( d == a[ m ] || e - s <= 1 ){
		return 1;
	}
	if( d > a[ m ] ){
		s = m;
	}
	if( d < a[ m ] ){
		e = m;
	}
	return 1 + find( a, s, e, d );
}

int main()
{
	int n;
	while( cin >> n && n ){
		int a[ 100 ] = {0};
		for( int i = 0; i < n; ++i ){
			cin >> a[ i ];
		}
		int d;
		cin >> d;
		cout << find( a, 0, n, d ) << endl;
	}

	return 0;
}

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

using namespace std;

int binary_search(int a[],int k,int n) {
	int l = 0, r = n-1, cnt=0;

	while (r - l >= 0) {
		int m = (l + r) / 2;
		cnt++;
		if (a[m] == k) return cnt;
		else if (a[m] > k) {
			r = m-1;
		}
		else if (a[m] < k) {
			l = m + 1;
		}
	}

	return cnt;
}

int main() {
	
	int n;

	while (cin>>n) {

		int a[100010], k, ans;

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

		cin >> k;

		ans=binary_search(a, k, n);

		cout << ans<<endl;
	}
}

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

int main()
{
  int n;
  while( cin >> n, n ) {
    int target;
    int cnt = 1;
    int l = 0, r = n-1, m;
    int data[100001];
   
    for(int i=0; i<n; i++) cin >> data[i];
    cin >> target;
    
   

    while( l != r ) {
      m = (l+r) / 2;
      if( data[m] == target ) break;
      if( target > data[m] ) l = m+1;
      else r = m-1;
      cnt++;
    }

    cout << cnt << endl;
  }

}