Comparing linear and binary searches

Although linear and binary searching produces the same overall results, linear search is best used when the data is not in order, or for smaller lists. However, when the list is much longer and the data is in order, it is far more efficient to calculate the needed to perform a binary search.

Linear v binary search example

Both could be used to search the following list for the number 7:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Linear search would require eight steps to find the search term in the list.

In a , this would look like:

Linear search trace table

Search term	Index	Data	Found	List
7	1	1	False	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	2	2	False	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	3	3	False	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	4	4	False	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	5	5	False	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	6	6	False	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	7	7	True	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term	7
Index	1
Data	1
Found	False
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term
Index	2
Data	2
Found	False
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term
Index	3
Data	3
Found	False
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term
Index	4
Data	4
Found	False
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term
Index	5
Data	5
Found	False
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term
Index	6
Data	6
Found	False
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term
Index	7
Data	7
Found	True
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

In contrast, binary search would take just four steps to find the same number.

In a trace table, this would look like:

Binary search trace table

Search term	Start	Index	Data	Found	List
7	1	10	5	False	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	6	10	8	False	[6, 7, 8, 9, 10]
	6	7	6	False	[6, 7]
	7	7	7	True	[7]

Search term	7
Start	1
Index	10
Data	5
Found	False
List	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Search term
Start	6
Index	10
Data	8
Found	False
List	[6, 7, 8, 9, 10]

Search term
Start	6
Index	7
Data	6
Found	False
List	[6, 7]

Search term
Start	7
Index	7
Data	7
Found	True
List	[7]

��ý

Searching and sorting algorithms - AQAComparing linear and binary searches