Efficient for finding an item in sorted data set Starts at middle in the list and repeatedly divides it in half Requires the list to be in order Efficient for large data sets Quickly reduces large data sets as it discards the other half of the list

Binary search in English

1Start at middle 2If middle = to be found, search over 3If to be found middle item, discard all to left 5Repeat from 2 till item found or no items left 6If item found output data, else “Not found”

Finds item in sorted/unsorted list Start at first item + compare each item to one being searched for, until found Fast for small set, slow for large, ideal for finding items in small sets Easiest searching alg to implement, but usually most inefficient

Linear search in English

1. Start at first item 2. If item in list is to be found, search over 3. If not, move to next item 4. Repeat from 2 until item is found or there are no more items in the list 5. If item found, output its data. If it has not, output “Not found”

Linear search in pseudocode

index = 0 found = false While found == False and index < items.Length If items[index] == item_to_find then found = True Else index = index + 1 End If End while

Help

Options

focusNode

Didn't know it?
click below

Knew it?
click below

Don't Know

Remaining cards (0)

Know

retry

shuffle

restart

0:00

Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

Search algs

1.3.1

Question	Answer
Binary search	Efficient for finding an item in sorted data set Starts at middle in the list and repeatedly divides it in half Requires the list to be in order Efficient for large data sets Quickly reduces large data sets as it discards the other half of the list
Binary search in English	1Start at middle 2If middle = to be found, search over 3If to be found < middle item, discard all to right 4If to be found > middle item, discard all to left 5Repeat from 2 till item found or no items left 6If item found output data, else “Not found”
Binary search in pseudocode
Linear search	Finds item in sorted/unsorted list Start at first item + compare each item to one being searched for, until found Fast for small set, slow for large, ideal for finding items in small sets Easiest searching alg to implement, but usually most inefficient
Linear search in English	1. Start at first item 2. If item in list is to be found, search over 3. If not, move to next item 4. Repeat from 2 until item is found or there are no more items in the list 5. If item found, output its data. If it has not, output “Not found”
Linear search in pseudocode	index = 0 found = false While found == False and index < items.Length If items[index] == item_to_find then found = True Else index = index + 1 End If End while

Created by: FlashCardFun!

"Know" box contains:
Time elapsed:
Retries: