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 <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

int n,a[100],t;

int main(){
	while(cin>>n&&n){
		rep(i,n)cin>>a[i];
		cin>>t;
		int lb=0,ub=n-1;
		int ans=0;
		while(++ans){
			//cout<<ans<<" "<<lb<<" "<<ub<<" "<<a[(lb+ub)/2]<<endl;
			if(a[(lb+ub)/2]==t||lb==ub){cout<<ans<<endl;break;}
			else if(a[(lb+ub)/2]<t)lb=(lb+ub)/2+1;
			else ub=(lb+ub)/2-1;
		}
	}
}

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

	return 0;
}

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

int main() {
  int n;
  while(cin >> n, n) {
    int target;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    cin >> target;

    int cnt = 1;
    bool b = false;
    int left = 0, right = n-1;
    while(left <= right) {
      int t = (right+left)/2;
      if(v[t] == target) {
        b = true;
        break;
      } else if(v[t] < target) {
        left = t+1;
      } else {
        right = t-1;
      }
      cnt++;
    }
    if(!b) cnt--;
    cout << cnt << endl;
  }
}

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

C++: //Name: Search
//Level: 2
//Category: 二分探索,シミュレーション
//Note:

/**
 * 問題文の通りに二分探索を実装し、比較回数を数える。
 *
 * オーダーは O(log N)。
 */

#include <iostream>
#include <vector>

using namespace std;

bool solve() {
    int N;
    if(!(cin >> N)) return false;
    if(!N) return false;

    vector<int> v(N);
    for(int i = 0; i < N; ++i) {
        cin >> v[i];
    }

    int Q;
    cin >> Q;
    int ans = 0;
    int l = 0, r = N-1;
    while(l <= r) {
        const int m = (l+r) / 2;
        ++ans;
        if(v[m] == Q) {
            break;
        } else if(v[m] < Q) {
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << ans << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while(solve()) ;
    return 0;
}

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;
		
		bool flag = false;
		int low = 0, high = n, mid = -1, cnt = 0, prev=0;
		while( true ){
			if( prev == mid ){
				flag = true;
				break;
			}
			
			cnt++;
			prev = mid;
			mid = (low + high) / 2;
			
			if( a[mid] == key ){
				break;
			}else if( a[mid] < key ){
				low = mid;
			}else{
				high = mid;
			}
		}
		if( flag ) cnt--;
		cout << cnt << endl;
	}
}

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 <iostream>
#include <algorithm>
using namespace std;
  
int T[100010];
int find(int m,int x){
    int r=0,l=m-1,ans=0;
    while(1){
        ans++;  
        if(r>=l)break;
        if(T[(r+l)/2]==x)return ans;
        if(T[(r+l)/2]>x)l=(r+l)/2-1;
        else if(T[(r+l)/2]<x)r=(r+l)/2+1;
if(r>l) break;
    }
    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 <cstdio>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cmath>
#include <queue>

using namespace std;

int a[100000];
int lef;
int rig;

int ans;

bool binary_search_2(int num){
	int middle = (lef + rig) / 2;
	if(rig - lef == 1){
		ans++;
		if(a[middle] != num){
			ans++;
		}
		return false;
	}
	if(rig == lef){
		ans++;
		return false;
	}
	ans++;
	if(a[middle] > num){
		rig = middle - 1;
		binary_search_2(num);
	}else if(a[middle] < num){
		lef = middle + 1;
		binary_search_2(num);
	}else if(a[middle] == num){
		return true;
	}
}

bool binary_search(int num, int n){
	lef = 0;
	rig = n - 1;
	binary_search_2(num);
}

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

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

using namespace std;

int nibo(int, vector<int>);

int main(void) {
	int n;
	vector<int> ans;

	while(true) {	
		cin >> n;
		if (n == 0) {
			break;
		}
		vector<int> data(n + 1 , 0);
		for (int i = 0; i < n + 1; i++) {
			cin >> data[i]; 
		}
		cout << nibo(n, data) << endl;
	}
       
	return 0;

}

int nibo(int n, vector<int> data) {
	int times = 0;
	int right = n - 1;
	int left = 0;
	int mid;
	int target = data[n];

	while(true) {
	        times++;
		mid = (right + left) / 2;
		if((right - left) <= 0){
			break;
		}
		if (data[mid] == target) {
			break;
		}
		if (data[mid] < target) {
			left = mid + 1;
		}
		if (data[mid] > target) {
			right = mid - 1;
		}
	}
		
		

	return times;

}

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