Searching Algorithms:

Linear Search:

If I had this array of numbers:

And I wanted to find the number ‘3’, a linear search would work like this:

• We look at the first value, in this case, ‘8’

• We assess if this is the required value, in this case, ‘3’

• If this is not the required value, then we move on to the next value. in this case, ‘5’

• We repeat these 3 steps until the value is found, or we come to the end of the array

• Each time we are looking at a new value, this is called a ‘parse’.

  • In this case, 6 parses are needed to find the number ‘3’ with a linear search

Binary Search:

If I had this array of numbers:

And I wanted to find the number ‘3’, a binary search would work like this:

• Firstly, we need to order the array in ascending order

• We find the middle value of this array by using the formula (n+1)/2, where n is the length of the array, in this case, 7.

  • For this array, we would be looking at the 4th value of ‘5’.

  • If this formula has a result of … .5 add another .5 to this to find the ideal value

• Once we have found the middle value, we need to assess whether this value is higher than, lower than or equal to the required value.

  • If this value is lower than the required value, we remove everything higher than and including this middle value.

  • If this value is higher than the required value, we remove everything lower than and including this middle value.

  • In this case, ‘5’ is higher than ‘3’, so we would remove the upper half of the array like so:

So we are left with:

• Next, we use steps 2 and 3 again on this new array

  • In this case, (n+1)/2 would result in us looking at the 2nd value of ‘2’.

• Again, we assess whether the value is higher than, lower than or equal to the required value

  • In this case, ‘2’ is lower than the required value so te 1st and 2nd values would be removed

• We continue this until we reach the required value

• Each time we divide, this is a new parse

  • In this case, 3 parses are needed to find the number ‘3’ with a binary search

Linear Search vs. Binary Search

Sorting Algorithms:

Bubble Sort:

If I had this array of numbers:

And I wanted to sort this array in ascending order, a bubble sort would work like this:

• We look at the 1st and 2nd values, in this case, ‘8’ and ‘5’

• If the value on the left is larger than the value on the right, we swap these. If not, we keep these how they are.

  • In this case, it would look like this:

• Next, we would look at the 2nd and 3rd values, in this case, ‘8’ and ‘9’.

• Again, if the value on the left is larger than the value on the right, we swap these. If not, we keep these how they are.

  • In this case, it would stay the same

• We continue this for each pair of values in the array.

  • In this case, it would look like this:

• Then again, we do this whole thing again

  • In this case, we would go from this:

To this:

• We keep repeating this until the array is fully ordered.

  • In this case, it would look like this:

• Then we complete one final parse to check that this is fully ordered correctly.

• Each time we sort through the whole array, this is a new parse

  • In this case, 6 parses are needed to sort this array into ascending order using binary search.

Merge Sort:

If I had this array of numbers:

And I wanted to sort this array in ascending order, a merge sort would work like this:

• We want to divide this array into 2 parts, of fairly equal length

  • In this case, as there is an odd number, one array shall be slightly longer

  • In this case, this would look like this:

• Then, we want to split these 2 arrays into another further 2

  • In this case, this would look like this:

• We continue this until each value is in its own array

  • In this case, this would look like this:

• Once all the values are separated, we want to merge these back together in ascending order. To do this, we merge each pair back together in ascending order.

  • In this case, this would look like this:

• We want to merge these again back to larger arrays in ascending order. We do not add one array after one another, but we order these whole small arrays.

  • In this case, this would look like this:

• We continue until we finish with one array.

  • In this case, this would look like this:

Bubble Sort vs. Merge Sort: