diff --git a/core/algorithm.hpp b/core/algorithm.hpp
new file mode 100644
index 0000000..5dc9dbb
--- /dev/null
+++ b/core/algorithm.hpp
@@ -0,0 +1,58 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NFD_CORE_ALGORITHM_HPP
+#define NFD_CORE_ALGORITHM_HPP
+
+#include "common.hpp"
+#include <boost/concept/requires.hpp>
+
+namespace nfd {
+
+/** \brief finds the last element satisfying a predicate
+ *  \tparam It BidirectionalIterator
+ *  \tparam Pred UnaryPredicate
+ *
+ *  \return Iterator to the last element satisfying the condition,
+ *          or \p last if no such element is found.
+ *
+ *  Complexity: at most \p last-first invocations of \p p
+ */
+template<typename It, typename Pred>
+BOOST_CONCEPT_REQUIRES(
+  ((boost::BidirectionalIterator<It>))
+  ((boost::UnaryPredicate<Pred, typename std::iterator_traits<It>::value_type>)),
+  (It)
+)
+find_last_if(It first, It last, Pred p)
+{
+  std::reverse_iterator<It> firstR(first), lastR(last);
+  auto found = std::find_if(lastR, firstR, p);
+  return found == firstR ? last : std::prev(found.base());
+}
+
+} // namespace nfd
+
+#endif // NFD_CORE_ALGORITHM_HPP
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index be6202c..584dda3 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -1,12 +1,12 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014,  Regents of the University of California,
- *                      Arizona Board of Regents,
- *                      Colorado State University,
- *                      University Pierre & Marie Curie, Sorbonne University,
- *                      Washington University in St. Louis,
- *                      Beijing Institute of Technology,
- *                      The University of Memphis
+ * Copyright (c) 2014-2015,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
  *
  * This file is part of NFD (Named Data Networking Forwarding Daemon).
  * See AUTHORS.md for complete list of NFD authors and contributors.
@@ -56,6 +56,13 @@
 }
 
 const Name&
+Entry::getName() const
+{
+  BOOST_ASSERT(!this->isQuery());
+  return m_data->getName();
+}
+
+const Name&
 Entry::getFullName() const
 {
   BOOST_ASSERT(!this->isQuery());
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index 12a65b0..a35d9e9 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -1,12 +1,12 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014,  Regents of the University of California,
- *                      Arizona Board of Regents,
- *                      Colorado State University,
- *                      University Pierre & Marie Curie, Sorbonne University,
- *                      Washington University in St. Louis,
- *                      Beijing Institute of Technology,
- *                      The University of Memphis
+ * Copyright (c) 2014-2015,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
  *
  * This file is part of NFD (Named Data Networking Forwarding Daemon).
  * See AUTHORS.md for complete list of NFD authors and contributors.
@@ -56,6 +56,9 @@
   getData() const;
 
   const Name&
+  getName() const;
+
+  const Name&
   getFullName() const;
 
   /** \return true if entry can become stale, false if entry is never stale
@@ -75,6 +78,9 @@
   void
   unsetUnsolicited();
 
+  /** \brief determines whether Interest can be satisified by this cached Data
+   *  \note ChildSelector is not considered
+   */
   bool
   canSatisfy(const Interest& interest) const;
 
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 822cb84..3bc816a 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -1,12 +1,12 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014,  Regents of the University of California,
- *                      Arizona Board of Regents,
- *                      Colorado State University,
- *                      University Pierre & Marie Curie, Sorbonne University,
- *                      Washington University in St. Louis,
- *                      Beijing Institute of Technology,
- *                      The University of Memphis
+ * Copyright (c) 2014-2015,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
  *
  * This file is part of NFD (Named Data Networking Forwarding Daemon).
  * See AUTHORS.md for complete list of NFD authors and contributors.
@@ -26,6 +26,7 @@
 #include "cs.hpp"
 #include "cs-entry.hpp"
 #include "core/logger.hpp"
+#include "core/algorithm.hpp"
 #include <numeric>
 
 NFD_LOG_INIT("ContentStore");
@@ -62,7 +63,7 @@
 bool
 Cs::insert(const Data& data, bool isUnsolicited)
 {
-  NFD_LOG_DEBUG("insert " << data.getFullName());
+  NFD_LOG_DEBUG("insert " << data.getName());
 
   bool isNewEntry = false; TableIt it;
   // use .insert because gcc46 does not support .emplace
@@ -88,50 +89,77 @@
   return true;
 }
 
-bool
-Cs::isNewRightmostCandidate(const Name& prefix, TableIt a, TableIt b)
-{
-  if (a->getFullName().size() == prefix.size()) {
-    return true;
-  }
-  return b->getFullName().at(prefix.size()) > a->getFullName().at(prefix.size());
-}
-
 const Data*
 Cs::find(const Interest& interest) const
 {
   const Name& prefix = interest.getName();
   bool isRightmost = interest.getChildSelector() == 1;
   NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
-  TableIt rightmostCandidate = m_table.end();
 
-  TableIt left = m_table.lower_bound(prefix);
-  TableIt right = m_table.end();
+  TableIt first = m_table.lower_bound(prefix);
+  TableIt last = m_table.end();
   if (prefix.size() > 0) {
-    right = m_table.lower_bound(prefix.getSuccessor());
+    last = m_table.lower_bound(prefix.getSuccessor());
   }
-  for (TableIt it = left; it != right; ++it) {
-    const Entry& entry = *it;
-    if (!entry.canSatisfy(interest)) {
-      NFD_LOG_TRACE("cannotSatisfy " << entry.getFullName());
-      continue;
-    }
-    NFD_LOG_TRACE("canSatisfy " << entry.getFullName());
-    if (!isRightmost) {
-      return entry.getData().get();
+
+  TableIt match = last;
+  if (isRightmost) {
+    match = this->findRightmost(interest, first, last);
+  }
+  else {
+    match = this->findLeftmost(interest, first, last);
+  }
+
+  if (match == last) {
+    NFD_LOG_DEBUG("  no-match");
+    return nullptr;
+  }
+  NFD_LOG_DEBUG("  matching " << match->getName());
+  return match->getData().get();
+}
+
+Cs::TableIt
+Cs::findLeftmost(const Interest& interest, TableIt first, TableIt last) const
+{
+  return std::find_if(first, last, bind(&cs::Entry::canSatisfy, _1, interest));
+}
+
+Cs::TableIt
+Cs::findRightmost(const Interest& interest, TableIt first, TableIt last) const
+{
+  // Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
+  // If there is a match in that sub-namespace, the leftmost match is returned;
+  // otherwise, loop continues.
+
+  size_t interestNameLength = interest.getName().size();
+  for (TableIt right = last; right != first;) {
+    TableIt prev = std::prev(right);
+
+    // special case: [first,prev] have exact Names
+    if (prev->getName().size() == interestNameLength) {
+      NFD_LOG_TRACE("  find-among-exact " << prev->getName());
+      TableIt matchExact = this->findRightmostAmongExact(interest, first, right);
+      return matchExact == right ? last : matchExact;
     }
 
-    if (rightmostCandidate == m_table.end() ||
-        isNewRightmostCandidate(prefix, rightmostCandidate, it)) {
-      NFD_LOG_TRACE("rightmostCandidate=" << entry.getFullName());
-      rightmostCandidate = it;
+    Name prefix = prev->getName().getPrefix(interestNameLength + 1);
+    TableIt left = m_table.lower_bound(prefix);
+
+    // normal case: [left,right) are under one-component-longer prefix
+    NFD_LOG_TRACE("  find-under-prefix " << prefix);
+    TableIt match = this->findLeftmost(interest, left, right);
+    if (match != right) {
+      return match;
     }
+    right = left;
   }
-  if (isRightmost) {
-    return rightmostCandidate == m_table.end() ? nullptr :
-                                 rightmostCandidate->getData().get();
-  }
-  return nullptr;
+  return last;
+}
+
+Cs::TableIt
+Cs::findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const
+{
+  return find_last_if(first, last, bind(&Entry::canSatisfy, _1, interest));
 }
 
 void
@@ -215,7 +243,7 @@
     TableIt it; std::string reason;
     std::tie(it, reason) = this->evictPick();
 
-    NFD_LOG_DEBUG("evict " << it->getFullName() << " " << reason);
+    NFD_LOG_DEBUG("evict " << it->getName() << " " << reason);
     this->detachQueue(it);
     m_table.erase(it);
   }
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 4eadd40..5bab097 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -1,12 +1,12 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014,  Regents of the University of California,
- *                      Arizona Board of Regents,
- *                      Colorado State University,
- *                      University Pierre & Marie Curie, Sorbonne University,
- *                      Washington University in St. Louis,
- *                      Beijing Institute of Technology,
- *                      The University of Memphis
+ * Copyright (c) 2014-2015,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
  *
  * This file is part of NFD (Named Data Networking Forwarding Daemon).
  * See AUTHORS.md for complete list of NFD authors and contributors.
@@ -118,10 +118,23 @@
   };
 
 private:
-  /** \brief determines whether b should be the rightmost candidate instead of a
+  /** \brief find leftmost match in [first,last)
+   *  \return the leftmost match, or last if not found
    */
-  static bool
-  isNewRightmostCandidate(const Name& prefix, TableIt a, TableIt b);
+  TableIt
+  findLeftmost(const Interest& interest, TableIt left, TableIt right) const;
+
+  /** \brief find rightmost match in [first,last)
+   *  \return the rightmost match, or last if not found
+   */
+  TableIt
+  findRightmost(const Interest& interest, TableIt first, TableIt last) const;
+
+  /** \brief find rightmost match among entries with exact Names in [first,last)
+   *  \return the rightmost match, or last if not found
+   */
+  TableIt
+  findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const;
 
   /** \brief attaches an entry to a suitable cleanup queue
    *  \note if the entry is already attached to a queue, it's automatically detached
diff --git a/tests/core/algorithm.cpp b/tests/core/algorithm.cpp
new file mode 100644
index 0000000..941166d
--- /dev/null
+++ b/tests/core/algorithm.cpp
@@ -0,0 +1,62 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "core/algorithm.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(CoreAlgorithm, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(FindLastIf)
+{
+  std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9};
+
+  int hit1 = 0;
+  std::vector<int>::const_iterator found1 = find_last_if(vec.begin(), vec.end(),
+      [&hit1] (int n) -> bool {
+        ++hit1;
+        return n % 2 == 0;
+      });
+  BOOST_REQUIRE(found1 != vec.end());
+  BOOST_CHECK_EQUAL(*found1, 8);
+  BOOST_CHECK_LE(hit1, vec.size());
+
+  int hit2 = 0;
+  std::vector<int>::const_iterator found2 = find_last_if(vec.begin(), vec.end(),
+      [&hit2] (int n) -> bool {
+        ++hit2;
+        return n < 0;
+      });
+  BOOST_CHECK(found2 == vec.end());
+  BOOST_CHECK_LE(hit2, vec.size());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd