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;

int main(void){
    int n;
    while(cin >> n, n){
        int data[10000];
        int need;
        for(int i=0; i < n; i++)
            cin >> data[i];
        cin >> need;

        int before = 0, after = n-1;
        int cnt = 0;
        while(before <= after){
            int mid = (after + before) / 2;
            cnt++;
            if(need == data[mid])
                break;
            if(data[mid] > need)
                after = mid-1;
            else
                before = mid+1;
        }
        cout << cnt << endl;
    }
    return 0;
}

C++: #include<stdio.h>
int n;
int a[100],sach;
int i;
int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		scanf("%d",&sach);
		int dai=n-1,syou=0;
		int now,cnt=0;
		while(syou<=dai){
			cnt++;
			now=(dai+syou)/2;
			if(a[now]==sach){
				break;
			}
			else if(a[now]<sach){
				syou=now+1;
			}
			else if(a[now]>sach){
				dai=now-1;
			}
		}
		printf("%d\n",cnt);
	}
	return 0;
}

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

int cnt;

int binary_search(int array[MAX],int key,int n){
    int left = 0 , right = n-1 , mid;
    
    while(left <= right){
        mid = (left+right)/2;
        if(array[mid]==key){
            cnt++;
            break;
        }
        else if(key < array[mid]){
            right = mid-1;
            cnt++;
        }
        else{
            left = mid+1;
            cnt++;
        }
    }

    return cnt;
}

int main(){
    int n,array[MAX],key;
    
    while(cin >> n,n){
        for(int i = 0 ; i < n ; i++) cin >> array[i];
        cin >> key;
        cnt = 0;
        cout << binary_search(array,key,n) << endl;
    }
    
    return 0;
}

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

int nibn(int a[], int s, int e, int k);
int nibn(int a[], int s, int e, int k){
	if(s>e) return 1;
	if(a[(s+e)/2] == k){
		return 1;
	}
	else if(a[(s+e)/2] < k){
		return 1 + nibn(a,(s+e)/2+1,e,k);
	}
	else if(a[(s+e)/2] > k){
		return 1 + nibn(a,s,(s+e)/2-1,k);
	}
}


int main(){
	int n, a[150], k;
	while(cin >> n){
		if(!n) break;
		for(int i = 0;i<n;i++){
			cin >> a[i];
		}
		cin >> k;
		cout << nibn(a,0,n-1,k) << endl;
	}
	return 0;
}

C++: #include <cstdio>
#define buf 1000001
using namespace std;
int cnt,b[buf];
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) break;
    for(i=0;i<a;i++){
      fgets(str,sizeof(str),stdin);
      sscanf(str,"%d",&n);
      b[i]=n;
    }
    for(i=0;i<a;i++)
      printf("%d ",b[i]);
    printf("\n");
    cnt=1;
    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;
  left = 0; right = a1;
  while(left < right){
    mid = (left + right)/2;
    if(b[mid] == n)
      break;
    else if(n < b[mid])
      right = mid;
    else if(n > b[mid])
      left = mid+1;
    cnt++;
  }
}

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;
		int lb=-1;
		int cnt=0;
		while(ub-lb>1){
			int mid=ub+lb;
			mid/=2;
			cnt++;
			if(nums[mid]==s){
				break;
			}
			else if(nums[mid]>s){
				ub=mid-1;
			}
			else if(nums[mid]<s){
				lb=mid+1;
			}
		}
		cout<<cnt+1<<endl;
	}

	return 0;
}

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

int main(){
  
  int n;
  int ans;
  // 無限ループさせる
  while(true){
    cin >> n;
    // n == 0
    if(n == 0){
      break;
    }

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

    // サーチする数
    int snum;
    cin >> snum;

    // search
    int top, last, center;
    top = 0;
    last = n - 1;
    ans = 0;
    while(top <= last){
      center = (top + last) / 2;
      ans++;
      // 一致？
      if(snum == num[center]){
	break;
      }
      
      if(snum > num[center]){
	top = center + 1;
      }
      else{
	last = center - 1;
      }
    }

    cout << ans << endl;
    
  }
  
  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 (void) {
    int n;
    int a[100];
    while(cin>>n && n){
        rep(i,n)cin>>a[i];
        int f;
        cin>>f;
        int l=0; int r=n-1;
        int ans=0;
        while(l<=r) {
            ans++;
            int m=(l+r)/2;
            if(a[m] == f) break;
            else if(a[m]<f)l=m+1;
            else r=m-1;
            m=(l+r)/2;
        }
        cout << ans << 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) {

		if (n == 0)
			return 0;

		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 <iostream>
#include<stdio.h>
using namespace std;

void search(int times);
void twice(int data[],int t, int target, int count);

void search(int times){
	int data[times-1] = {0};
	int target, count=0;
	for(int i=0;i<times-1;i++){
		cin >> data[i];
	}
	cin >> target;
	

	return twice(data, times-1, target, count);
}

void twice(int data[],int t, int target, int count){
	
	if(t == 1 || t == 0){
		count++;
		cout << count <<endl;
	} else {

	
	int times = t/2;
	if(data[times] < target){
		int dataN[times] = {};
		for(int i=0;i<times;i++){
			if(t % 2 == 1){
				dataN[i]=data[i+times+1];
			} else if(t % 2 == 0){
				dataN[i] = data[i+times];
			}
		}

		count++;
		twice(dataN,times, target, count);

	} else if(data[times] > target){
		int dataN[times] = {};
		for(int i=0;i<times;i++){
			dataN[i]=data[i];
		}
		count++;
		twice(dataN,times, target, count);
	} else if(data[times] == target){
		cout << count << endl;
	}
}
}

int main() {
	int i;
	while(1) {
		cin >> i;
		//cout << res << endl;
		if(i == 0){
			break;
		}

		search(i+1);
	}
	return 0;
}

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

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

int main() {
  int hi,lo,m,n,a,i,k,d[100];
  while(cin >> n && n!=0) {
	  for (i=0;i<n;i++) cin >> d[i];
	  cin >> a;
	  hi=n-1; lo=k=0;
	  while(true) {
	  k++; m=(hi+lo)/2; 
	  if (d[m]>a) lo=m-1; else if (d[m]<a) hi=m+1; else break;
	  if (hi==lo) { k++; break;}
	   }
	  cout << k << endl;
  }
  return 0;
}