Searching
30th Jan 20
Parity bit
This can be used as a check to see if there is an even or odd number of 1's in a binary number E.G
_0110101 To if you need it to be even and it is currently odd, then you will put a 1 to make it even.
E.G _1100101 there is 4 1's here and it needs to be odd, so i will add a 5th 1 to make the parity odd.
Linear search
A linear search is use when you have an unordered list and you need to find a value or item in the list and by using a linear search you go to the first item and ask is it the number you are looking for, if yes then you stop searching, if no then you continue to search in this manor asking the next item until you find the item you find the item you need or you reach the end and the item you are looking for isn't there.
E.G. I need the number 42 in the following list. 23, 29, 34 , 37, 40, 42, 57.
I go to the first number is it 42, No then i go to the second number in the list is this one 42, No then i go to the third number in the list is this one 42, No then i go to the fourth number in the list is this one 42, No then i go to the fifth number in the list is this one 42, No then i go to the sixth number in the list is this one 42, Yes then i stop searching.
Binary search
You would use a binary search in an ordered list to find the item in the list that you want. In this search you will go half way through you numerically or alphabetically ordered list and ask are you my number, if Yes stop if No then ask if your item is higher or low then go to the higher or lower half and forget about the other one, continue this until you reach your number.
E.G. I need 7 out of the number 1 to 10
1 Go to half way (5), is this my number ? No is my number higher or lower ? Higher, now forget about the halfway point and the lower numbers.
2 Repeat until you get to your number
So now go to 8, is this my number , No so is my number higher or lower, lower then forget about 8,9,10. now i have 6 and 7, go to one of them and ask is his my number no then is the other one my number if yes for either stop other wise your number isn't in the list.
Bubble sort
1. Take the first element and the second from the list
2. Compare them
3. If element 1 > element 2 THEN
- then swap them
4. Else
- Do nothing
5 REPEAT: Move along the list to the next pair
- If no more elements: GO TO element 1
- Else: GO TO element 2
Until: You have moved through the entire list and NOT made any changes
E.G.
2, 4, 3 ,1.
2 is smaller than 4, leave it there. 4 is larger than 3 so swap them around.(now the list is 2,3,4,1)
4 is larger than 1 so swap them (list is now 2,3,1,4). 2 is smaller than 3 leave them. 3 is larger than 1 so swap them. 4 is the largest, so leave it (list is now 2,1,3,4). 2 is larger than 1 so swap them 3 is bigger than 2 so we leave it, now we go over and check, now it is numerically correct.
Merging list
This is when you split a list down to individuals and then put them in an order.
E.G.
F,P,A,L,T,D,K,H My list
1 Split the list into half until all elements are individuals
F P A L and T D K H
then
F P and AL and T D and K H
then
F P A L T D K H
2 Now out of the pairs put it in alphabetical or numerical order.
FP AL DT HK
3 Now put them into two lists in alphabetical or numerical order, by taking the first of each pair and putting them into the correct places between them.
A F L P and D H K T
4 Then put it back the way you did with the pairs.
A D F H K L P T.
Now do these:
Merge these two lists
3,7,8,10,11 4,6,8,13
and
2,19,3,45,77,10,25,29,60,1
Parity bit
This can be used as a check to see if there is an even or odd number of 1's in a binary number E.G
_0110101 To if you need it to be even and it is currently odd, then you will put a 1 to make it even.
E.G _1100101 there is 4 1's here and it needs to be odd, so i will add a 5th 1 to make the parity odd.
Linear search
A linear search is use when you have an unordered list and you need to find a value or item in the list and by using a linear search you go to the first item and ask is it the number you are looking for, if yes then you stop searching, if no then you continue to search in this manor asking the next item until you find the item you find the item you need or you reach the end and the item you are looking for isn't there.
E.G. I need the number 42 in the following list. 23, 29, 34 , 37, 40, 42, 57.
I go to the first number is it 42, No then i go to the second number in the list is this one 42, No then i go to the third number in the list is this one 42, No then i go to the fourth number in the list is this one 42, No then i go to the fifth number in the list is this one 42, No then i go to the sixth number in the list is this one 42, Yes then i stop searching.
Binary search
You would use a binary search in an ordered list to find the item in the list that you want. In this search you will go half way through you numerically or alphabetically ordered list and ask are you my number, if Yes stop if No then ask if your item is higher or low then go to the higher or lower half and forget about the other one, continue this until you reach your number.
E.G. I need 7 out of the number 1 to 10
1 Go to half way (5), is this my number ? No is my number higher or lower ? Higher, now forget about the halfway point and the lower numbers.
2 Repeat until you get to your number
So now go to 8, is this my number , No so is my number higher or lower, lower then forget about 8,9,10. now i have 6 and 7, go to one of them and ask is his my number no then is the other one my number if yes for either stop other wise your number isn't in the list.
Bubble sort
1. Take the first element and the second from the list
2. Compare them
3. If element 1 > element 2 THEN
- then swap them
4. Else
- Do nothing
5 REPEAT: Move along the list to the next pair
- If no more elements: GO TO element 1
- Else: GO TO element 2
Until: You have moved through the entire list and NOT made any changes
E.G.
2, 4, 3 ,1.
2 is smaller than 4, leave it there. 4 is larger than 3 so swap them around.(now the list is 2,3,4,1)
4 is larger than 1 so swap them (list is now 2,3,1,4). 2 is smaller than 3 leave them. 3 is larger than 1 so swap them. 4 is the largest, so leave it (list is now 2,1,3,4). 2 is larger than 1 so swap them 3 is bigger than 2 so we leave it, now we go over and check, now it is numerically correct.
Merging list
This is when you split a list down to individuals and then put them in an order.
E.G.
F,P,A,L,T,D,K,H My list
1 Split the list into half until all elements are individuals
F P A L and T D K H
then
F P and AL and T D and K H
then
F P A L T D K H
2 Now out of the pairs put it in alphabetical or numerical order.
FP AL DT HK
3 Now put them into two lists in alphabetical or numerical order, by taking the first of each pair and putting them into the correct places between them.
A F L P and D H K T
4 Then put it back the way you did with the pairs.
A D F H K L P T.
Now do these:
Merge these two lists
3,7,8,10,11 4,6,8,13
and
2,19,3,45,77,10,25,29,60,1
Comments
Post a Comment