Programming – Pascal: Essential skills 2

 

Learning Outcomes:

Apply algorithms of counting, accumulating, swapping, searching, sorting and merging in writing programs.

Searching a list

 

Sequential search: check one by one.

Binary search:

 

Principles:

A sorted list in ascending or descending order. (otherwise cannot use binary search)

i	1	2	3	4	5	6
A[i]	50	95	105	205	400	450

Question 1: Where is 205 located?

Sequential search: check one by one from i = 1 to 6.

Binary search: check middle one to see. (1+6)/2 = 3. A[3] = 105.

105 < 205 i.e. ignore the left side and check the right side only à i from 4 to 6 (lower bound changed) Senario 1

i	1	2	3	4	5	6
A[i]	50	95	105	205	400	450

Check the middle one again. (4+6)/2 = 5. A[5] = 400.

400>205 i.e. ignore the right side and check the left side only à i from 4 to 4 (upper bound changed) Senario 2

i	1	2	3	4	5	6
A[i]	50	95	105	205	400	450

Check the middle one again. (4+4)/2 = 4. A[4] = 205. à found!

 

Question 2: What would happen if we instead look for 200 in the list?

After 2nd round, we check the middle one again. (4+4)/2 = 4. A[4] = 205.

205 > 200 i.e. Ignore the right side and check the left side only à i from 4 to 3 (upper bound changed) à implies 200 not in the list. Senario 3

 

Techniques:

Suppose you have an array A[i] with i = 1 to n. You want to find location of x in A[i].

var                 min, max, mid : integer;                 found : boolean; begin                 min := 1;                 max := n;                 found := false;                                                   (* to stop the loop once the target found*)                 repeat                                 mid := (min + max) div 2;                               (* calculate the middle of the list *)                                 if A[mid] = x then found := true                                                 else if A[mid] > x then max := mid -1        (* Senario 2 *)                                                 else min := mid + 1;                         (* Senario 1 *)                 until found or (min > max);                                          (* Senario 3 min > max *)                 If found then writeln (mid) end.

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2015 3d*.

CE CIT Elect A(2005-2011): 2006 2.