Бинарный поиск

int l = min значение
int r = max значение (эти переменные можно сделать и вещественными)
for (int i = 0; i < n; i++) {
 int mid = (l+r)/2;
 if (g(mid)) // функция g монотонна b и возращает true или false
  l = mid;
 else 
  r = mid;
}

int bin_search(int key,int size)
{
    if(size == 0 || arr[0]>key || arr[size-1]<key)
        return -1;
    int first=0,last=size-1,mid;
    while(first < last)
    {
        mid=first + ((last-first)>>1);
        if(arr[mid] == key)
            return mid;
        else if(arr[mid] > key)
            last=mid-1;
        else
            first=mid+1;
    }
    if(arr[last]==key)
        return last;
    else
        return -1;
}

#include <cstring>
#include <iostream>
#include <fstream>
 
template <class ForwardIterator, class T, class Compare>
ForwardIterator lowerBound (ForwardIterator first, ForwardIterator last,
  const T& value, Compare compare) {
  size_t count = last - first;
  while (count > 0) {
    ForwardIterator it = first;
    size_t step = count / 2;
    it += step;
    if (compare(*it, value)) {
      first = ++it;
      count -= step + 1;
    } else {
      count = step;
    }
  }
  return first;
}
 
class SortedStrings {
 public:
  typedef char **Iterator;
  typedef char *const *ConstIterator;
  SortedStrings() : capacity(10), size(0), strings(new char*[capacity]) {}
  virtual ~SortedStrings() {
    clear();
    delete [] strings;
  }
  void clear() {
    for (size_t i = 0; i < size; ++i) {
      delete [] strings[i];
    }
    size = 0;
  }
  size_t getSize() const { return size; }
  ConstIterator insert(const char *string) {
    checkCapacity(1);
    Iterator position = lowerBound(strings, strings + size, string,
      lesserString);
    for (Iterator i = strings + size; i > position; --i) {
      *i = *(i - 1);
    }
    *position = strcpy(new char[strlen(string) + 1], string);
    ++size;
    return position;
  }
  void remove(ConstIterator position) {
    size_t offset = position - strings;
    delete [] strings[offset];
    for (Iterator i = strings + offset; i < end(); ++i) {
      *i = *(i + 1);
    }
    --size;
  }
  ConstIterator begin() { return strings; }
  ConstIterator end() { return strings + size; }
  bool contains(const char *string) {
    Iterator position = lowerBound(strings, strings + size, string,
      lesserString);
    return position != end() && !lesserString(string, *position);
  }
 private:
  static bool lesserString(const char *a, const char *b) {
    return strcmp(a, b) < 0;
  }
  void checkCapacity(int increment) {
    if (capacity < capacity + increment) {
      capacity += increment;
      char **newData = new char*[capacity];
      for (size_t i = 0; i < size; ++i) {
        newData[i] = strings[i];
      }
      delete [] strings;
      strings = newData;
    }
  }
  size_t capacity;
  size_t size;
  char **strings;
};
 
int main(int argc, char *argv[]) {
  SortedStrings s;
  
  std::ifstream input("names.txt");
 
  while (!input.eof()) {
    char buffer[1024];
    input.getline(buffer, sizeof(buffer) - 1);
    if (!input.eof()) {
      s.insert(buffer);
    }
  }
  
  for (SortedStrings::ConstIterator i = s.begin(); i != s.end(); ++i) {
    std::cout << *i << std::endl;
  }
 
  char searchable[] = "Anna Annovna";
  std::cout << "Sorted string list " <<
    (s.contains(searchable) ? "contains '" : "does not contain '") <<
    searchable << "'" << std::endl;
 
  return 0;
}