Index: ELF/SyntheticSections.cpp
===================================================================
--- ELF/SyntheticSections.cpp
+++ ELF/SyntheticSections.cpp
@@ -2434,16 +2434,17 @@
   std::vector<GdbIndexSection::NameAttrEntry> Ret;
   for (const DWARFSection *Pub : {&PubNames, &PubTypes}) {
     DWARFDebugPubTable Table(Obj, *Pub, Config->IsLE, true);
-    uint32_t I = 0;
     for (const DWARFDebugPubTable::Set &Set : Table.getData()) {
       // The value written into the constant pool is Kind << 24 | CuIndex. As we
       // don't know how many compilation units precede this object to compute
       // CuIndex, we compute (Kind << 24 | CuIndexInThisObject) instead, and add
       // the number of preceding compilation units later.
-      //
-      // We assume both CUs[*].CuOff and Set.Offset are increasing.
-      while (I < CUs.size() && CUs[I].CuOffset < Set.Offset)
-        ++I;
+      uint32_t I =
+          lower_bound(CUs, Set.Offset,
+                      [](GdbIndexSection::CuEntry CU, uint32_t Offset) {
+                        return CU.CuOffset < Offset;
+                      }) -
+          CUs.begin();
       for (const DWARFDebugPubTable::Entry &Ent : Set.Entries)
         Ret.push_back({{Ent.Name, computeGdbHash(Ent.Name)},
                        (Ent.Descriptor.toBits() << 24) | I});
Index: test/ELF/gdb-index-multiple-cu.s
===================================================================
--- test/ELF/gdb-index-multiple-cu.s
+++ test/ELF/gdb-index-multiple-cu.s
@@ -3,20 +3,27 @@
 # RUN: ld.lld --gdb-index %t.o -o %t
 # RUN: llvm-dwarfdump -gdb-index %t | FileCheck %s
 
-# Attributes << 24 | CuIndex = 48 << 24 | 1 = 0x30000001
-# CHECK: Constant pool
-# CHECK-NEXT: 0(0x0): 0x30000001
+# CuIndexAndAttrs of _start:
+#   Attributes << 24 | CuIndex = 48 << 24 | 0 = 0x30000000
+# CuIndexAndAttrs of foo:
+#   Attributes << 24 | CuIndex = 48 << 24 | 1 = 0x30000001
+# CHECK:      Symbol table
+# CHECK-DAG:      String name: _start, CU vector index: 0
+# CHECK-DAG:      String name: foo, CU vector index: 1
+# CHECK:      Constant pool
+# CHECK-NEXT:   0(0x0): 0x30000000
+# CHECK-NEXT:   1(0x8): 0x30000001
 
-.globl _start
+.globl _start, foo
 _start:
-	ret
+foo:
 
 .section .debug_abbrev,"",@progbits
 	.byte	1              # Abbreviation Code
 	.byte	17             # DW_TAG_compile_unit
 	.byte	1              # DW_CHILDREN_yes
 	.ascii	"\264B"        # DW_AT_GNU_pubnames
-	.byte	12             # DW_FORM_flag
+	.byte	25             # DW_FORM_flag_present
 	.byte	0              # EOM(1)
 	.byte	0              # EOM(2)
 	.byte	2              # Abbreviation Code
@@ -34,8 +41,11 @@
 	.short	4              # DWARF version number
 	.long	0              # Offset Into Abbrev. Section
 	.byte	4              # Address Size
+.Ldie0:
 	.byte	1              # Abbrev [1] DW_TAG_compile_unit
-	.byte	0              # DW_AT_GNU_pubnames
+	.byte	2              # Abbrev [2] DW_TAG_subprogram
+	.asciz	"_start"       # DW_AT_name
+	.byte	0
 	.byte	0
 .Lcu_end0:
 .Lcu_begin1:
@@ -43,23 +53,36 @@
 	.short	4              # DWARF version number
 	.long	0              # Offset Into Abbrev. Section
 	.byte	4              # Address Size
-.Ldie:
+.Ldie1:
 	.byte	1              # Abbrev [1] DW_TAG_compile_unit
-	.byte	1              # DW_AT_GNU_pubnames
 	.byte	2              # Abbrev [2] DW_TAG_subprogram
-	.asciz	"_start"       # DW_AT_name
+	.asciz	"foo"          # DW_AT_name
 	.byte	0
 .Lcu_end1:
 
-# .debug_gnu_pubnames has just one set, associated with .Lcu_begin1 (CuIndex: 1)
+# Swap sets to test the case where pubnames are in a
+# different order than the CUs they refer to.
 .section .debug_gnu_pubnames,"",@progbits
-	.long	.LpubNames_end1-.LpubNames_begin1
+	# CuIndex: 1
+	.long	.LpubNames_end1 - .LpubNames_begin1
 .LpubNames_begin1:
 	.short	2              # Version
 	.long	.Lcu_begin1    # CU Offset
 	.long	.Lcu_end1 - .Lcu_begin1
-	.long	.Ldie - .Lcu_begin1
+	.long	.Ldie1 - .Lcu_begin1
 	.byte	48             # Attributes: FUNCTION, EXTERNAL
-	.asciz	"_start"       # External Name
+	.asciz	"foo"          # External Name
 	.long	0
 .LpubNames_end1:
+
+	# CuIndex: 0
+	.long	.LpubNames_end0 - .LpubNames_begin0
+.LpubNames_begin0:
+	.short	2              # Version
+	.long	.Lcu_begin0    # CU Offset
+	.long	.Lcu_end0 - .Lcu_begin0
+	.long	.Ldie0 - .Lcu_begin0
+	.byte	48             # Attributes: FUNCTION, EXTERNAL
+	.asciz	"_start"       # External Name
+	.long	0
+.LpubNames_end0: