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 <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/2;
	int ans = 0;
	int b = 0;
	while (1){
	    if (p == s && p == e) break;
	    if (*p == search) break;
	    else if (*p > search){
		e = p;
		p = s + (e - s)/2;
	    }
	    else if (*p < search){
		s = p+1;
		p = s + (e - s)/2 + 1;
	    }

	    ans++;
	}

	cout << ans << endl;
    }
}

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){
			cnt++;
			if(lb<0||ub<0||ub>=n||lb>=n||ub<lb)
				break;
			int mid=ub+lb;
			mid/=2;
			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 <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(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<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 (a[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<iostream>
using namespace std;
int main(){
    int n,a[101],X;
    while(1){
    cin >> n;
    if(n==0)break;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    cin >> X;
    int high=n-1,low=0,cnt=0;
    while(high>=low){
        cnt++;
        int center=(low+high)/2;
        if(a[center]==X) break;
        else if(a[center]<X) low=center+1;
        else high=center-1;
    }
    cout << cnt << 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;
      cnt++;
      if( data[m] == target ) break;
      if( target > data[m] ) l = m+1;
      else r = m-1;
    }

    cout << cnt << endl;
  }

}

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

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


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 - 1, d ) << endl;
	}

	return 0;
}

C++: #include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;
const int INF = 1 << 30;

int main()
{
	int n;

	while(cin >> n)
	{
		vector<int> T;
		int res = 0, num, up = n-1, low = 0;
		for(int i = 0; i < n; i++)
		{
			int a; cin >> a;
			T.push_back(a);
		}
		cin >> num;

		while( low <= up )
		{
			int mid = (up + low) / 2;
			res++;
			if(T[mid] > num)
			{
				up = mid-1;
			}
			else if(T[mid] < num)
			{
				low = mid+1;
			}
			else
			{
				break;
			}
		}
		
		cout << res << endl;
	}
}

C++: #include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define INF 1000000001
#define MOD 10000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const ull B=100000007;
int main(){
      int n;
      while(cin>>n&&n){
            int r=n-1,l=0,a[n],cnt=0,k;
            REP(i,n)cin>>a[i];
            cin>>k;
            while(r!=l){
                  int mid=(r+l)/2;
                  cnt++;
                  if(k==a[mid])break;
                  if(k>a[mid])l=mid+1;
                  else r=mid-1;
            }
            cout<<cnt+1<<endl;
      }
}

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

int main(){
	int *data, n, key, count, p, l, c;
	while(true){
		std::cin >> n;
		if(n==0)
			return 0;
		data = new int[n];
		for(int i=0; i<n; i++)
			std::cin >> data[i];
		std::sort(data, data+n);
		std::cin >> key;
		p=0, l=n-1,count = 0;
		while(p<=l){
			count++;
			c = (p+l)/2;
			if(data[c] == key && p==l){
				count--;
				break;
			}
			if(data[c] > key)
				p = c+1;
			else
				l = c-1;
		}
		count++;
		std::cout << count << std::endl;
		delete[] data;
	}
}

C++: #include<iostream>

using namespace std;

int main()
{
	int n,i,j;
	int serch,array[100];
	
	for(;;)
	{
		cin >> n ;
		if(n==0)
			break;
		
		for(i=0;i<n;i++)
			cin >> array[i] ;
		cin >> serch ;
		
		int count=1;
		
		for(j=0;j<n;j++)
		{
			if(array[(n-j)/2+j]==serch)
				break;
			if(array[(n-j)/2+j]<serch)
				j=(n-j)/2+j;
			else
				n=(n-j)/2+j;
			count++;
		}
		
		cout << count << endl;
	}
}

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){
			if(ub<lb)
				break;
			cnt++;
			int mid=ub+lb;
			mid/=2;
			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;
}