For Example, the data is:
The key is 2
The key is 2
Record | [1] | [2] | [3] | [4] | [5] |
Data | 2 | 5 | 21 | 1 | 6 |
First step: the data must be sorting. This sample, we can sort the data with bubble sort methods.
Record | [1] | [2] | [3] | [4] | [5] | |
Data | 2 | 5 | 21 | 1 | 6 | |
Step 1 | 2 | 5 | 21 | 1 | 6 | 2 and 5, no Exchange |
2 | 5 | 21 | 1 | 6 | 2 and 21, no Exchange | |
1 | 5 | 21 | 2 | 6 | 2 and 1, Exchange | |
Step 2 | 1 | 5 | 21 | 2 | 6 | 5 and 21, no Exchange |
1 | 2 | 21 | 5 | 6 | 2 and 5, Exchange | |
Step 3 | 1 | 2 | 5 | 21 | 6 | 5 and 21, Exchange |
Step 4 | 1 | 2 | 5 | 6 | 21 | 21 and 6, Exchange |
Second step: we can search data key 2 with binary search
New data:
Record | [1] | [2] | [3] | [4] | [5] |
Data | 1 | 2 | 5 | 6 | 21 |
Step [1]:
(low+high) div 2 = (1+5) div 2
= 6 div 2
= 3
the data on the record [3] is 5, then 5>3, next step swipe left
Step [2]: new_high = middle-1 =3 - 1 = 2
(low + new_high) div 2 = (1+2) div 2
= 3 div 2
= 1
the data on the record [1] is 1, then 1<2, next step swipe right
Step [3]: new_low = low + 1 = 2
(new_low + new_high) div 2 = (2+2) div 2
= 4 div 2
= 2
the data on the record [2] is 2, end.
low | middle | high | |||
Record | [1] | [2] | [3] | [4] | [5] |
Data | 1 | 2 | 5 | 6 | 21 |
Step [2]: new_high = middle-1 =3 - 1 = 2
(low + new_high) div 2 = (1+2) div 2
= 3 div 2
= 1
the data on the record [1] is 1, then 1<2, next step swipe right
low | new_high | ||||
Record | [1] | [2] | [3] | [4] | [5] |
Data | 1 | 2 | 5 | 6 | 21 |
Step [3]: new_low = low + 1 = 2
(new_low + new_high) div 2 = (2+2) div 2
= 4 div 2
= 2
new_low=new_high | |||||
Record | [1] | [2] | [3] | [4] | [5] |
Data | 1 | 2 | 5 | 6 | 21 |
the data on the record [2] is 2, end.
No comments:
Post a Comment
Note: only a member of this blog may post a comment.