Da die Sammlung nicht sortiert ist, muss man sie vollständig durchsuchen. Wenn man dies z.B. von links nach rechts macht, so stösst man im schlechtesten Fall erst an letzter Stelle auf das gesuchte Album. Es könnte aber auch sein, dass es bereits die erste CD ist. Im Durchschnitt muss man die Hälfte der Alben durchsuchen, hier 64 Stück. Der Aufwand der linearen Suche, auch sequenzielle Suche genannt, ist proportional mit der Anzahl Objekte. D.h. wenn es doppelt so viele Alben hat, muss man doppelt so lange suchen.
Die lineare Suche hat also eine Komplexität von O(n/2). » O-Notation

Die Sammlung ist alphabetisch sortiert und lässt einem das gesuchte Album schnell finden, da man feststellen kann, ob der gesuchte Eintrag weiter vorne oder weiter hinten zu finden ist. Dieses Verfahren lässt sich systematisieren:

• Nimm das mittlere Element.
• Ist dieses Element das gesuchte, so ist die Suche erfolgreich beendet.
• Ist dieses Element das einzig verbliebene, so ist die Suche erfolglos beendet.
• Ist das gefundene Element grösser als das gesuchte, so fahre mit Schritt i. für die linke Hälfte, sonst für die rechte Hälfte weiter.

Bei einer Sammlung von 128 Elementen zeigt die folgende Grafik ein möglicher Weg der wiederholten Halbierung:

Im Extremfall bleibt am Schluss genau ein Album übrig. Entweder ist dieses das gesuchte oder die gesuchte CD kommt in der Sammlung nicht vor.
Das binäre Suchverfahren nimmt auf sich selbst Bezug (vgl. Punkt iv.) und ist folglich rekursiv. Zudem weist dieses Verfahren dank der fortschreitenden Halbierung der Suchbreite mit O(log₂(n)) eine grosse Effizient auf. Dies zeigt auch die folgende Tabelle. » O-Notation

Anzahl Objekte	Anzahl Halbierungen
2	1
4	2
8	3
16	4
32	5
64	6
128	7
256	8
512	9
1'024	10
1'048'576	20
1'073'741'824	30