מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/חיפוש לינארי ובינרי/תרגילים/מציאת מספר בינרי חסר/תשובה

נתבונן בעמודה האחרונה, ונספור את מספר ה0-ים ומספר ה1-ות שאנו רואים. היות שיש $\displaystyle m=2^{n}-1$, שורות, אז מספר ה0-ים גדול ב1 ממספר ה1-ות, או הפוך. נניח שמספר ה0-ים גדול ב1 ממספר ה1-ות (המקרה השני סימטרי). נוכל להסיק שני דברים:

1. הספרה החסרה בעמודה זו היא 1.
2. עלינו להתמקד רק בשורות בהן הספרה בעמודה זו היא 1 (קומבינטורית, לא ייתכן אחרת).

כעת נתחיל את הבעיה מחדש, תוך התמקדות בחצי (בערך) מהשורות (רק אלה בהן הספרה בעמודה זו היא 1): נסתכל בעמודה הלפני אחרונה,נספור את מספר ה0-ים ומספר ה1-ות שאנו רואים , וכולי.

להלן פסוודו-קוד יעיל המממש זאת:

Print-Missing-Number(M)
1	n = Num-Cols(M)

2	Rows = Make-Stack()

3	for j in [1, … 2^n - 1]
4		Insert-Front(Rows, j)
	
5	for i in [1, … n]
6		Zeros = Make-Stack()
7		Ones = Make-Stack()
	
8		while Size(Rows) > 0
9			row = Pop(Rows)
		
10			if M[row][i] == 0
11				Push(Zeros, row)
12			else
13				Push(Ones, row)
			
14		if Size(Zeros) > Size(Ones)
15			Print(1)
16			Rows = Ones
17		else
18			Print(0)
19			Rows = Zeros

1-4 מאתחלות את המחסנית Rows כך שתכיל את כל (מספרי השורות). 5-19 עובורת על כל העמודות. בכל איטרציה, 8-13 מחלקות את מספרי השורות בRows לשתי מחסניות, לפי ערך ביט העמודה הנכחית. 14-19 מדפיסות את הביט החסר בעמודה הנכחית, ומחליטות באיזו משתי המחסניות להתמקד.

נותר לנתח הסיבוכיות. נשים לב שהאיטרציה הראשונה פועלת בזמן $\displaystyle \Theta (m)$, האיטרציה השניה בזמן $\displaystyle \Theta (m/2)$, ובאופן כללי, האיטרציה ה$\displaystyle i$ בזמן $\displaystyle \Theta (m/2^{i})$. זמן הריצה, לכן, הוא $\displaystyle \sum _{i=1}^{n}\left[\Theta (m/2^{i})\right]=\Theta (m).$