# Algorithms 2.1 Searches and sorts Flashcards

Describe the steps a binary search will follow to look for a number in a sorted list

Find the middle item in the ordered list.

check if selected number is equal to / matches target number

if this is the item you are looking for, then stop the search - since the number has been found

if this item is not equal to the target item then check:

if searched number is larger, then discard left half

if searched number is smaller, then discard right half

Repeat this process until the number or item is found or

remaining list is of size 1 / 0 (which shows number was not found/ or number was not in list)

there are no more items to be found (remaining list is of size 1 or 0)

Examples of Standard searching algorithms:

Binary search

Linear search

What are binary search and linear search examples of

Examples of Standard searching algorithms:

Use the binary search algorithm to find he number 8 in the following list

3 6 8 11 13 15 18

Middle item = (7 + 1) /2 = 4th item

4th item = 11

compare 11 to 8

11 > 8 so split left

Items in list: 3,6,8

Middle item = (3+1)/2 = 2nd item = 6

compare 6 to 8

6 < 8 so split right

Items in the list: 8

8 is the last item in the list

Middle item = (1+1)/2 = 1st item = 8

Stop searching as 8 has been found

Show the stages of a binary search to find the word ‘zebra’ when applied to the data shown

amber, house, kick, moose, orange, range, tent, wind, zebra

middle item = (9 + 1) / 2 = 5th item

5th item = orange

compare zebra to orange

zebra > orange, so split right

middle item = (4+1)/2 = 2.5 rounds up to 3rd item

3rd item = Wind

compare zebra to wind

zebra>wind, so split right

Zebra is the last item in the list OR Middle item = (1+1)/2 = 1st item = Zebra

Compare zebra to zebra

Zebra = Zebra

Item has been found

Middle item = (1+1)/2 = 1st item = Zebra

Describe the steps a linear search would follow when searching for a number that is not in the given list.

Starting with the first value

Checking all values in order

Describe the steps a linear search

1) look at the first item in the unordered list

2) is this is the item you are looking for, then stop the search - the item has been found

3) if not, then look at the next item in the list

repeat steps 2) - 3) until you find the item that you are looking for or you have checked every item (this shows that the item was not in the list)

Use linear search to find “11” in the list

3 6 8 11 13 15 18

Starting with the first value

Check each item in order:

Check 1st item: 3 ≠ 11 move to the next item in the list

Check 2nd item: 6 ≠ 11 move to the next item in the list

Check 3rd item: 8 ≠ 11 move to the next item in the list

Check 4th item: 11 = 11

Stop searching as 11 has been found

Nicoa has a list of numbers

2 3 7 5 13 11

She says, “I can’t use a binary search to find 13” Why is this the case

A binary search only works on ordered data

file:///C:/Users/44748/Documents/The%20code%20for%20all%20the%20searching%20and%20sorting%20algorithms.pdf

file:///C:/Users/44748/Documents/The%20code%20for%20all%20the%20searching%20and%20sorting%20algorithms.pdf

Standard sorting algorithms:

o Bubble sort

o Merge sort

o Insertion sort

o Bubble sort

o Merge sort

o Insertion sort

are examples of

Standard sorting algorithms

Merge sort is an example of ______

divide and conquer algorithm

describe the steps to bubble sort

1)look at the first two items in the list

2) if they are in the right order, you dont have to do anything

If they are in the wrong order, swap them

3) move on to the next pair of items (the 2nd and 3rd items) and repeat step 2).

4) repeat step 3) until you get to the end of the list - this is called one pass

The last item will now be in the correct place, so dont include it in the next pass

5) Repeat steps 1) - 4) until there are no swaps in a pass

describe the steps to merge sort

1) split the list in half (the smaller lists are called sub lists) - the second sub-list should start at the middle item

2) keep repeating step 1) on each sub-list until all the lists only contain one item

3) merge pairs of sub-lists so that each sub-list has twice as many items

Each time you merge sub-lists, sort the items into the right order