diff --git a/libunwindstack/DwarfEhFrameWithHdr.cpp b/libunwindstack/DwarfEhFrameWithHdr.cpp
index 668527a..802beca 100644
--- a/libunwindstack/DwarfEhFrameWithHdr.cpp
+++ b/libunwindstack/DwarfEhFrameWithHdr.cpp
@@ -61,6 +61,14 @@
   table_encoding_ = data[3];
   table_entry_size_ = memory_.template GetEncodedSize<AddressType>(table_encoding_);
 
+  // If we can't perform a binary search on the entries, it's not worth
+  // using this object. The calling code will fall back to the DwarfEhFrame
+  // object in this case.
+  if (table_entry_size_ == 0) {
+    last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
+    return false;
+  }
+
   memory_.set_pc_offset(memory_.cur_offset());
   if (!memory_.template ReadEncodedValue<AddressType>(ptr_encoding_, &ptr_offset_)) {
     last_error_.code = DWARF_ERROR_MEMORY_INVALID;
@@ -137,13 +145,13 @@
 }
 
 template <typename AddressType>
-bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetBinary(uint64_t pc, uint64_t* fde_offset,
-                                                          uint64_t total_entries) {
-  CHECK(fde_count_ > 0);
-  CHECK(total_entries <= fde_count_);
+bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetFromPc(uint64_t pc, uint64_t* fde_offset) {
+  if (fde_count_ == 0) {
+    return false;
+  }
 
   size_t first = 0;
-  size_t last = total_entries;
+  size_t last = fde_count_;
   while (first < last) {
     size_t current = (first + last) / 2;
     const FdeInfo* info = GetFdeInfoFromIndex(current);
@@ -172,87 +180,6 @@
 }
 
 template <typename AddressType>
-bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetSequential(uint64_t pc, uint64_t* fde_offset) {
-  CHECK(fde_count_ != 0);
-  last_error_.code = DWARF_ERROR_NONE;
-  last_error_.address = 0;
-
-  // We can do a binary search if the pc is in the range of the elements
-  // that have already been cached.
-  if (!fde_info_.empty()) {
-    const FdeInfo* info = &fde_info_[fde_info_.size() - 1];
-    if (pc >= info->pc) {
-      *fde_offset = info->offset;
-      return true;
-    }
-    if (pc < info->pc) {
-      return GetFdeOffsetBinary(pc, fde_offset, fde_info_.size());
-    }
-  }
-
-  if (cur_entries_offset_ == 0) {
-    // All entries read, or error encountered.
-    return false;
-  }
-
-  memory_.set_data_offset(entries_data_offset_);
-  memory_.set_cur_offset(cur_entries_offset_);
-  memory_.set_pc_offset(0);
-  cur_entries_offset_ = 0;
-
-  FdeInfo* prev_info = nullptr;
-  for (size_t current = fde_info_.size();
-       current < fde_count_ && memory_.cur_offset() < entries_end_; current++) {
-    FdeInfo* info = &fde_info_[current];
-    uint64_t value;
-    if (!memory_.template ReadEncodedValue<AddressType>(table_encoding_, &value) ||
-        !memory_.template ReadEncodedValue<AddressType>(table_encoding_, &info->offset)) {
-      fde_info_.erase(current);
-      last_error_.code = DWARF_ERROR_MEMORY_INVALID;
-      last_error_.address = memory_.cur_offset();
-      return false;
-    }
-
-    // Relative encodings require adding in the load bias.
-    if (IsEncodingRelative(table_encoding_)) {
-      value += load_bias_;
-    }
-    info->pc = value;
-
-    if (pc < info->pc) {
-      if (prev_info == nullptr) {
-        return false;
-      }
-      cur_entries_offset_ = memory_.cur_offset();
-      *fde_offset = prev_info->offset;
-      return true;
-    }
-    prev_info = info;
-  }
-
-  if (fde_count_ == fde_info_.size() && pc >= prev_info->pc) {
-    *fde_offset = prev_info->offset;
-    return true;
-  }
-  return false;
-}
-
-template <typename AddressType>
-bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetFromPc(uint64_t pc, uint64_t* fde_offset) {
-  if (fde_count_ == 0) {
-    return false;
-  }
-
-  if (table_entry_size_ > 0) {
-    // Do a binary search since the size of each table entry is fixed.
-    return GetFdeOffsetBinary(pc, fde_offset, fde_count_);
-  } else {
-    // Do a sequential search since each table entry size is variable.
-    return GetFdeOffsetSequential(pc, fde_offset);
-  }
-}
-
-template <typename AddressType>
 void DwarfEhFrameWithHdr<AddressType>::GetFdes(std::vector<const DwarfFde*>* fdes) {
   for (size_t i = 0; i < fde_count_; i++) {
     const FdeInfo* info = GetFdeInfoFromIndex(i);
diff --git a/libunwindstack/DwarfEhFrameWithHdr.h b/libunwindstack/DwarfEhFrameWithHdr.h
index e3e9ca8..0e5eef7 100644
--- a/libunwindstack/DwarfEhFrameWithHdr.h
+++ b/libunwindstack/DwarfEhFrameWithHdr.h
@@ -69,10 +69,6 @@
 
   const FdeInfo* GetFdeInfoFromIndex(size_t index);
 
-  bool GetFdeOffsetSequential(uint64_t pc, uint64_t* fde_offset);
-
-  bool GetFdeOffsetBinary(uint64_t pc, uint64_t* fde_offset, uint64_t total_entries);
-
   void GetFdes(std::vector<const DwarfFde*>* fdes) override;
 
  protected:
diff --git a/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp b/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp
index 910ae36..be9e721 100644
--- a/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp
+++ b/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp
@@ -95,6 +95,13 @@
   EXPECT_EQ(0x1000U, this->eh_frame_->TestGetEntriesDataOffset());
   EXPECT_EQ(0x100aU, this->eh_frame_->TestGetCurEntriesOffset());
 
+  // Verify a zero table entry size fails to init.
+  this->memory_.SetData8(0x1003, 0x1);
+  ASSERT_FALSE(this->eh_frame_->Init(0x1000, 0x100, 0));
+  ASSERT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->eh_frame_->LastErrorCode());
+  // Reset the value back to the original.
+  this->memory_.SetData8(0x1003, DW_EH_PE_sdata4);
+
   // Verify a zero fde count fails to init.
   this->memory_.SetData32(0x1006, 0);
   ASSERT_FALSE(this->eh_frame_->Init(0x1000, 0x100, 0));
@@ -276,9 +283,8 @@
   EXPECT_EQ(0x500U, info->offset);
 }
 
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetBinary_verify) {
+TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_verify) {
   this->eh_frame_->TestSetTableEntrySize(0x10);
-  this->eh_frame_->TestSetFdeCount(10);
 
   typename DwarfEhFrameWithHdr<TypeParam>::FdeInfo info;
   for (size_t i = 0; i < 10; i++) {
@@ -288,105 +294,42 @@
   }
 
   uint64_t fde_offset;
-  EXPECT_FALSE(this->eh_frame_->GetFdeOffsetBinary(0x100, &fde_offset, 10));
+  this->eh_frame_->TestSetFdeCount(10);
+  EXPECT_FALSE(this->eh_frame_->GetFdeOffsetFromPc(0x100, &fde_offset));
   // Not an error, just not found.
   ASSERT_EQ(DWARF_ERROR_NONE, this->eh_frame_->LastErrorCode());
   // Even number of elements.
   for (size_t i = 0; i < 10; i++) {
+    SCOPED_TRACE(testing::Message() << "Failed at index " << i);
     TypeParam pc = 0x1000 * (i + 1);
-    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc, &fde_offset, 10)) << "Failed at index " << i;
-    EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
-    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 1, &fde_offset, 10))
-        << "Failed at index " << i;
-    EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
-    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 0xfff, &fde_offset, 10))
-        << "Failed at index " << i;
-    EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
+    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc, &fde_offset));
+    EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 1, &fde_offset));
+    EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 0xfff, &fde_offset));
+    EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
   }
+
   // Odd number of elements.
+  this->eh_frame_->TestSetFdeCount(9);
   for (size_t i = 0; i < 9; i++) {
+    SCOPED_TRACE(testing::Message() << "Failed at index " << i);
     TypeParam pc = 0x1000 * (i + 1);
-    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc, &fde_offset, 9)) << "Failed at index " << i;
-    EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
-    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 1, &fde_offset, 9))
-        << "Failed at index " << i;
-    EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
-    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 0xfff, &fde_offset, 9))
-        << "Failed at index " << i;
-    EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
+    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc, &fde_offset));
+    EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 1, &fde_offset));
+    EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+    EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 0xfff, &fde_offset));
+    EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
   }
 }
 
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetBinary_index_fail) {
+TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_index_fail) {
   this->eh_frame_->TestSetTableEntrySize(0x10);
   this->eh_frame_->TestSetFdeCount(10);
 
   uint64_t fde_offset;
-  EXPECT_FALSE(this->eh_frame_->GetFdeOffsetBinary(0x1000, &fde_offset, 10));
-}
-
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetSequential) {
-  this->eh_frame_->TestSetFdeCount(10);
-  this->eh_frame_->TestSetEntriesDataOffset(0x100);
-  this->eh_frame_->TestSetEntriesEnd(0x2000);
-  this->eh_frame_->TestSetTableEncoding(DW_EH_PE_udata4);
-
-  this->memory_.SetData32(0x1040, 0x340);
-  this->memory_.SetData32(0x1044, 0x500);
-
-  this->memory_.SetData32(0x1048, 0x440);
-  this->memory_.SetData32(0x104c, 0x600);
-
-  // Verify that if entries is zero, that it fails.
-  uint64_t fde_offset;
-  ASSERT_FALSE(this->eh_frame_->GetFdeOffsetSequential(0x344, &fde_offset));
-  this->eh_frame_->TestSetCurEntriesOffset(0x1040);
-
-  ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x344, &fde_offset));
-  EXPECT_EQ(0x500U, fde_offset);
-
-  ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x444, &fde_offset));
-  EXPECT_EQ(0x600U, fde_offset);
-
-  // Expect that the data is cached so no more memory reads will occur.
-  this->memory_.Clear();
-  ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x444, &fde_offset));
-  EXPECT_EQ(0x600U, fde_offset);
-}
-
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetSequential_last_element) {
-  this->eh_frame_->TestSetFdeCount(2);
-  this->eh_frame_->TestSetEntriesDataOffset(0x100);
-  this->eh_frame_->TestSetEntriesEnd(0x2000);
-  this->eh_frame_->TestSetTableEncoding(DW_EH_PE_udata4);
-  this->eh_frame_->TestSetCurEntriesOffset(0x1040);
-
-  this->memory_.SetData32(0x1040, 0x340);
-  this->memory_.SetData32(0x1044, 0x500);
-
-  this->memory_.SetData32(0x1048, 0x440);
-  this->memory_.SetData32(0x104c, 0x600);
-
-  uint64_t fde_offset;
-  ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x540, &fde_offset));
-  EXPECT_EQ(0x600U, fde_offset);
-}
-
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetSequential_end_check) {
-  this->eh_frame_->TestSetFdeCount(2);
-  this->eh_frame_->TestSetEntriesDataOffset(0x100);
-  this->eh_frame_->TestSetEntriesEnd(0x1048);
-  this->eh_frame_->TestSetTableEncoding(DW_EH_PE_udata4);
-
-  this->memory_.SetData32(0x1040, 0x340);
-  this->memory_.SetData32(0x1044, 0x500);
-
-  this->memory_.SetData32(0x1048, 0x440);
-  this->memory_.SetData32(0x104c, 0x600);
-
-  uint64_t fde_offset;
-  ASSERT_FALSE(this->eh_frame_->GetFdeOffsetSequential(0x540, &fde_offset));
-  ASSERT_EQ(DWARF_ERROR_NONE, this->eh_frame_->LastErrorCode());
+  EXPECT_FALSE(this->eh_frame_->GetFdeOffsetFromPc(0x1000, &fde_offset));
 }
 
 TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_fail_fde_count) {
@@ -397,7 +340,7 @@
   ASSERT_EQ(DWARF_ERROR_NONE, this->eh_frame_->LastErrorCode());
 }
 
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_binary_search) {
+TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_search) {
   this->eh_frame_->TestSetTableEntrySize(16);
   this->eh_frame_->TestSetFdeCount(10);
 
@@ -417,26 +360,6 @@
   EXPECT_EQ(0x10700U, fde_offset);
 }
 
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_sequential_search) {
-  this->eh_frame_->TestSetFdeCount(10);
-  this->eh_frame_->TestSetTableEntrySize(0);
-
-  typename DwarfEhFrameWithHdr<TypeParam>::FdeInfo info;
-  info.pc = 0x50;
-  info.offset = 0x10000;
-  this->eh_frame_->TestSetFdeInfo(0, info);
-  info.pc = 0x150;
-  info.offset = 0x10100;
-  this->eh_frame_->TestSetFdeInfo(1, info);
-  info.pc = 0x250;
-  info.offset = 0x10200;
-  this->eh_frame_->TestSetFdeInfo(2, info);
-
-  uint64_t fde_offset;
-  ASSERT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(0x200, &fde_offset));
-  EXPECT_EQ(0x10100U, fde_offset);
-}
-
 TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetCieFde32) {
   // CIE 32 information.
   this->memory_.SetData32(0xf000, 0x100);
@@ -526,10 +449,8 @@
 REGISTER_TYPED_TEST_CASE_P(DwarfEhFrameWithHdrTest, Init, Init_non_zero_load_bias, GetFdes,
                            GetFdeInfoFromIndex_expect_cache_fail, GetFdeInfoFromIndex_read_pcrel,
                            GetFdeInfoFromIndex_read_datarel, GetFdeInfoFromIndex_cached,
-                           GetFdeOffsetBinary_verify, GetFdeOffsetBinary_index_fail,
-                           GetFdeOffsetSequential, GetFdeOffsetSequential_last_element,
-                           GetFdeOffsetSequential_end_check, GetFdeOffsetFromPc_fail_fde_count,
-                           GetFdeOffsetFromPc_binary_search, GetFdeOffsetFromPc_sequential_search,
+                           GetFdeOffsetFromPc_verify, GetFdeOffsetFromPc_index_fail,
+                           GetFdeOffsetFromPc_fail_fde_count, GetFdeOffsetFromPc_search,
                            GetCieFde32, GetCieFde64, GetFdeFromPc_fde_not_found);
 
 typedef ::testing::Types<uint32_t, uint64_t> DwarfEhFrameWithHdrTestTypes;