2.3.4 Searching Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

Which searching algorithm requires data to be sorted?

A

Binary search

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the time complexity of binary search?

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the time complexity of linear search?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Outline the stages of a binary search.

A

Compare the middle element with item to be found
If not found, move to left half (smaller) or right half (greater)
Repeat until found or no more items to search

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Outline the stages of a linear search.

A

First item examined
If not found, next item examined
Repeated until found or end of list reached

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What data sets does linear search work best for?

A

Unordered, small data sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What data sets does binary search work best for?

A

Ordered, large data sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly