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)
	}
}

Python: def search(n,d,t):
    b = 0
    e = n-1
    r = 0
    while True:
        if b > e:
            return r
        else:
            r += 1
            i = (b+e)//2
            if t == d[i]:
                return r
            elif t < d[i]:
                e = i - 1
            else:
                b = i + 1
while True:
    n = int(input())
    if n == 0:
        break
    d = [int(input()) for i in range(n)]
    t = int(input())

    m = search(n,d,t)
    print(m)

Python: while 1:
    n = int(input())
    if n == 0:
        break

    array = []
    for _ in range(n):
        a = int(input())
        array.append(a)
    k = int(input())

    n -= 1
    l = 0
    cnt = 0
    while l <= n:
        cnt += 1
        m = (l+n) // 2
        if array[m] == k:
            break

        if array[m] < k:
            l = m + 1
        else:
            n = m - 1
    print(cnt)

Python: while 1:
    l,r=0,int(input())
    if r==0:break
    a=[int(input()) for _ in range(r)]
    r-=1;c=0
    k=int(input())
    while l<=r:
        c+=1
        m=(l+r)//2
        if a[m]==k:break
        if a[m]<k:l=m+1
        else:r=m-1
    print(c)

C++: #include <iostream>

using namespace std;

#define MAX_N 101

int a[MAX_N];

int main() {
    int n, f;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> f;
        int count = 0;
        int r = 0, l = n-1;
        int mid;
        while (true) {
            if (r == l) {
                count++;
                break;
            }
            mid = (r+l) / 2;
            count++;
            if (a[mid] == f) {
                break;
            } else if (a[mid] < f) {
                r = mid+1;
            } else if (a[mid] > f) {
                l = mid-1;
            }
        }
        cout << count << endl;
    }
    return 0;
}

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

C++: #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        int num[n],ans;
        for(int i=0;i<n;i++)cin>>num[i];
        cin>>ans;
        int serch=n/2,kawa[2]={0,n};
        for(int i=1;;i++){
            if(num[serch]==ans||n/2+1==i){
                cout<<i<<endl;
                break;
            }
            else if(num[serch]>ans){
                    kawa[1]=serch;
                    serch=(kawa[0]+kawa[1])/2;
            }
            else {
                    kawa[0]=serch+1;
                    serch=(kawa[0]+kawa[1])/2;
            }
        }
    }
}

C++: #include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main() {
	int n, x;
	while (1) {
		cin >> n;
		if (n == 0) break;
		vi d(n);
		rep(i, 0, n) {
			cin >> d[i];
		}
		cin >> x;
		int cnt = 0, l = 0, r = n - 1;
		while (1) {
			int mid = (l + r) / 2;
			cnt++;
			if (r == l) break;
			if (d[mid] > x) {
				r = mid - 1;
			}
			else if (d[mid] < x) {
				l = mid + 1;
			}
			else if (d[mid] == x) {
				break;
			}
		}
		cout << cnt << endl;
	}
}

C++: #define _CRT_SECURE_NO_WARNINGS

#include<fstream>
#include<iostream>
#include<string>
#include<iomanip>
#include<list>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

int main(){
	int n = 0;
	int num[100];
	while (cin >> n && n != 0) {
		int now = n >> 1;
		int n_cnt = n;
		int sea;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		cin >> sea;
		while (n_cnt > 0) {
			cnt++;
			n_cnt = n_cnt >> 1;
			if (num[now] == sea) {
				break;
			}
			else if (num[now] > sea) {
				now -= (n_cnt - (n_cnt >> 1));
			}
			else {
				now += (n_cnt - (n_cnt >> 1));
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        int num[n],ans;
        for(int i=0;i<n;i++)cin>>num[i];
        cin>>ans;
        int serch=n/2;
        for(int i=0;;i++){
            if(num[serch]==ans||i==n-1){
                cout<<i<<endl;
                break;
            }
            else if(num[serch]>ans)serch=serch/2;
            else serch=(n+serch)/2;
        }
    }
}

C++: //
#include <iostream>
#include <math.h>
using namespace std;




int main(){
    int a, b, times;
    int i1, tyuusinn, yousosuu, yousosuu2;
    while(1){
    cin >> a;
    if(a==0){break;}
    i1=0;
        times=0;
    int w[a];
    while(1){
        cin >> b;
        w[i1]=b;
        i1++;
        if(i1==a)break;
    }
    sort(w, w+a);
    cin >> b;
    yousosuu=a;
    
    tyuusinn=yousosuu/2;
        while(1){
    times++;
    yousosuu2=yousosuu/2;
    if(w[tyuusinn]==b){break;}
    else if(w[tyuusinn]>b){
        tyuusinn=tyuusinn-yousosuu/2+yousosuu2/2;
        yousosuu=yousosuu2;
    }
    else{
        if(yousosuu%2==0){
            tyuusinn=tyuusinn+yousosuu2/2;
            yousosuu=yousosuu2-1;
        }
        else{
            tyuusinn=tyuusinn+yousosuu2/2+1;
            yousosuu=yousosuu2;
        }
    }
            if(yousosuu==0){break;}
        }
        
    cout << times << 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;
  //sort(data,data+n);
  while(1){
    ans++;
    int now = (start+end)/2;
    //cout <<"now  "  <<now << endl;
    if(data[now] == wanted || start >= end) break;
    if(data[now] > wanted) end = now;
    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 <vector>
using namespace std;

vector<int> arr;
int n;

int main(void){
  while(cin >> n, n){
    int num;
    arr.clear();
    for(int i = 0; i < n; i++){
      cin >> num;
      arr.push_back(num);
    }
    int search, cnt = 0;
    cin >> search;
    int lb = 0, ub = n - 1;
    while(lb <= ub){
      int mid = (lb + ub) / 2;
      cnt++;
      if(arr[mid] == search){
        break;
      }if(arr[mid] > search){
        ub = mid - 1;
      }else{
        lb = mid + 1;
      }
    }
    cout << cnt << endl;
  }
  return 0;
}