自作の二分探索のバグが取れない

Question

イテレータを返す二分探索を書いているのですが、mid, distなどの加減をどう変えてみても正しく判定されないものがいくつか出てきます。
std::distanceの呼び出しを1度で抑えるのが目的なので、できればwhile内の条件分岐部分を直す方法が知りたいです。
どうすれば良いでしょうか?

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

#include <functional>
#include <iostream>
#include <vector>
typedef std::vector<int>::const_iterator Iterator;

template<class Compare>
Iterator BinarySearch(Iterator begin, Iterator end, Compare comp) {
  auto dist = std::distance(begin, end);
  auto it = begin;
  auto not_found = end;

  while (dist > 0) {
    auto mid = it;
    dist /= 2;
    std::advance(mid, dist);
    auto comp_result = comp(*mid);

    if (comp_result == 0) {
      return mid;
    } else if (comp_result < 0) {  // *midが探索対象より小さい
      it = ++mid;
      --dist;
    } else {  // *midが探索対象より大きい
      end = --mid;
      --dist;
    }
  }

  return not_found;
}

int main() {
  std::vector list1{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  std::vector list2{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
  std::vector test_numbers{-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};

  auto bin_search_wrapper = [](std::vector<int> &list, int target) {
    return BinarySearch(std::begin(list),
                        std::end(list),
                        [target](const int &cur) {
                          if (cur < target) {
                            return -1;
                          } else if (cur == target) {
                            return 0;
                          }
                          return 1;
                        });
  };

  std::cout << "Test BinarySearch()\n" << "list1{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}\n";
  for (const auto &n : test_numbers) {
    if (auto it = bin_search_wrapper(list1, n); it != std::end(list1)) {
      std::cout << n << ": found" << "\n";
    } else {
      std::cout << n << ": not found" << "\n";
    }
  }
  std::cout << "\nlist2{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}\n";
  for (const auto &n : test_numbers) {
    if (auto it = bin_search_wrapper(list2, n); it != std::end(list2)) {
      std::cout << n << ": found" << "\n";
    } else {
      std::cout << n << ": not found" << "\n";
    }
  }
}

Comments

[episteme]

これ、12223 から 2 を探すと 真ん中の2 をみつけますよね。
ひとつみつけたらそこで検索終了していいんですか?
最も左寄り(or右寄り)の2 をみつけなくていいんですか?

[退会済みユーザー]

そこまで考えていませんでした。確かに今のままだと実用的ではありませんね。
左寄り(あるいは右寄り)を得るには、どういう操作を追加すればよいのでしょうか?

[episteme]

「一致しても二分法を止めない」じゃねぇの?

Answer 1

これでもよいようですが。

template<class Compare>
Iterator BinarySearch(Iterator begin, Iterator end, Compare comp) {
  auto not_found = end;
  int dist;

  while ((dist = end - begin)) > 0) {
	auto mid = begin + dist / 2;
    auto comp_result = comp(*mid);

    if (comp_result < 0) // *midが探索対象より小さい
	  begin = mid + 1;
    else if (comp_result > 0) // *midが探索対象より大きい
	  end = mid;
    else
	  return mid;
  }
  return not_found;
}

Comments

[退会済みユーザー]

簡潔で良いですね。
C++ではwhile()内で代入ができるとは知りませんでした。

Answer 2

  while (dist > 0) {
    auto mid = it;
    auto be_even = dist % 2 == 0;
    dist /= 2;
    std::advance(mid, dist);
    auto comp_result = comp(*mid);

    if (comp_result == 0) {
      return mid;
    } else if (comp_result < 0) {  // *midが探索対象より小さい
      it = ++mid;
      if(be_even) --dist;
    } else {  // *midが探索対象より大きい
      end = mid;
    }
  }