Я не могу написать бинарный поиск

// Pre: (0 <= left) and (right < v.size()) and (v is sorted in an ascending order)
// Post: returns a number i, left<=i<=right and v[i]==x.
//		 If there is no element x in v[], returns -1.
int position(double x, const vector<double>& v, int left, int right) {
    if (left > right) return -1;
    int pos = (left + right)/2; // the middle of v[left,right]
    if (x < v[pos]) return position(x, v, left, pos - 1);
    if (x > v[pos]) return position(x, v, pos + 1, right);
    return pos;
}

int[] data;
int getIndex(int left, int right, int x) {
  while (right-left>1) {
    int middle=(left+right)/2; // обычно не нужно больше 10^9 элементов.
    if (data[middle]>=x) {
      left=middle;
    } else {
      right=middle;
    }
  }
  return left;
}

# coding: utf-8

class Element:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __str__(self):
        return "%d (%s)" % (self.key, self.value)

# Обычный бинарный поиск
def BinSearch(arr, elem, l, u):
    if not arr:
        return -1

    while True:
        if u < l:
            return -1
        i = (l + u) / 2
        if elem.key < arr[i].key:
            u = i - 1
        elif elem.key > arr[i].key:
            l = i + 1
        else:
            return i

array = [Element(key, chr((key % 26) + 65,) ) for key in [1, 7, 11, 12, 24, 123]]
key = 12

print "array =", map(str, array)
print "key = %d" % key
print "index =", BinSearch(array, Element(key, "value"), 0, len(array) - 1)

raw_input("Press any key...")

array = ['1 (B)', '7 (H)', '11 (L)', '12 (M)', '24 (Y)', '123 (T)']
key = 12
index = 3
Press any key...

        static int BinSearch(int[] m,int a,int kf) {
            int len=m.Length;
            int cf=0;
            if(len==0) return -1;
            if(m[0]>m[len-1]) {
                a=~a; cf=-1;
            }
            int x1=-1,x2=len;
            while(x2-x1>1) {
                int x3=x1+(x2-x1)/2;
                int h=m[x3]^cf;
                if(h==a && kf==0) return x3;
                if(kf<0 ? h>=a : h>a) x2=x3;
                else x1=x3;
            }
            if(kf<0) {
                if(x2<len && (m[x2]^cf)==a) return x2;
            } else {
                if(x1>=0 && (m[x1]^cf)==a) return x1;
            }
            return ~x2;
        }

        static int BinarySearch(List<int> list, int num, Tuple<int, int> range)
        {
            int midleIndex = (range.Item1 + range.Item2) / 2;
            Func<int>[,] funcs = new Func<int>[,]
                                    {
                                        {
                                            () => -1, () => -1, () => -1
                                        },
                                        {
                                            () => BinarySearch(list, num, new Tuple<int, int>(range.Item1, midleIndex)),
                                            () => midleIndex,
                                            () => BinarySearch(list, num, new Tuple<int, int>(midleIndex + 1, range.Item2))
                                        }
                                    };
            return funcs[(1 + Math.Sign(1 + 2 * (list.Count - range.Item2))) * Math.Sign(range.Item2 - range.Item1) / 2, Math.Sign(num - list[midleIndex]) + 1]();
        }

#include <vector>
#include <iterator>
#include <iostream>

namespace bs {
    namespace impl {
        template<typename E, bool find_first>
        typename std::vector<E>::const_iterator find(const std::vector<E>& where, const E& what, const typename std::vector<E>::const_iterator& begin, const typename std::vector<E>::const_iterator& end)
        {
            typename std::vector<E>::const_iterator::difference_type size = std::distance(begin, end);
            if (size == 0)
                return where.end();

            typename std::vector<E>::const_iterator center = begin + size / 2;
            if (what < *center)
                return find<E, find_first>(where, what, begin, center);
            if (*center < what)
                return find<E, find_first>(where, what, center+1, end);
            if (find_first) {
                typename std::vector<E>::const_iterator leftmost = find<E, find_first>(where, what, begin, center);
                if (leftmost != where.end())
                    return leftmost;
            }
            return center;
        }
    };

    template<typename E, bool find_first>
    typename std::vector<E>::const_iterator find(const std::vector<E>& where, const E& what)
    {
        return impl::find<E, find_first>(where, what, where.begin(), where.end());
    }
};

int main(int argc, char* argv[])
{
    std::vector<int> input = { 10, 21, 34, 34, 34, 35, 41, 45, 49, 67, 102, 120, 120, 120, 120, 120, 120, 201 };
    std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl << std::endl;

    int what;
    for(;;) {
        std::cout << "Find what: ";
        std::cin >> what;

        typename std::vector<int>::const_iterator found = bs::find<int, true>(input, what);
        if (found == input.end()) {
            std::cout << "Not found" << std::endl;
            continue;
        }

        std::cout << "Found at " << std::distance(static_cast<std::vector<int>::const_iterator>(input.begin()), found) << std::endl;
    }

    return 0;
}

• (left; right) — интервал;
• [left; right] — отрезок.