Linear seach and Binary seach - Педагогика - Рефераты

Информация о документе

Цена	2000UZS
Размер	27.5KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Рефераты
Предмет	Педагогика

Linear seach and Binary seach

Купить

Linear seach and Binary seach
1 What is “linear search”.
2 An efficient method in Binary search.
3 Bubble sort.
Linear search
A linear search is the simplest method of searching
a data set.
Starting at the beginning of the data set, each item of
data is examined until a match is made. Once the
item is found, the search ends.
A way to describe a linear search would be:
1. Find out the length of the data set.
2. Set counter to 0.
3. Examine value held in the list at the counter
position.
4. Check to see if the value at that position matches
the value searched for.
5. If it matches, the value is found. End the search.
6. If not, increment the counter by 1 and go back to
step 3 until there are no more items to search.
Consider this list of unordered numbers:

Suppose we were to search for the value 2. The
search would start at position 0 and check the value
held there, in this case 3.
3 does not match 2, so we move on to the next
position.
The value at position 1 is 5.
5 does not match 2, so we move on to the next
position.
The value at position 2 is 2 - a match. The search
ends.
A linear search in pseudocode might look like this:
A linear search, although simple, can be quite
inefficient. Suppose the data set contained 100 items
of data, and the item searched for happens to be the
last item in the set? All of the previous 99 items
would have to be searched through first.
However, linear searches have the advantage that
they will work on any data set, whether it is ordered
or unordered.
Binary search
A binary search is an efficient method of searching
an ordered list.
A binary search works like this:

1. Start by setting the counter to the middle position
in the list.
2. If the value held there is a match, the search ends.
3. If the value at the midpoint is less than the value
to be found, the list is divided in half. The lower
half of the list is ignored and the search keeps to
the upper half of the list.
4. Otherwise, if the value at the midpoint is greater
than the value to be found, the upper half of the
list is ignored and the search keeps to the lower
half of the list.
5. The search moves to the midpoint of the
remaining items. Steps 2 through 4 continue until
a match is made or there are no more items to be
found.
Consider this list of ordered numbers:
Suppose we were to search for the value 11.
The midpoint is found by adding the lowest position
to the highest position and dividing by 2.
Highest position (8) + lowest position (0) = 8
8/2 = 4
NOTE - if the answer is a decimal, round up. For
example, 3.5 becomes 4. We can round down as an
alternative, as long as we are consistent.

Check at position 4, which has the value 7.
7 is less than 11, so the bottom half of the list
(including the midpoint) is discarded.
The new lowest position is 5.
Highest position (8) + lowest position (5) = 13
13/2 = 6.5, which rounds up to 7
Check at position 7, which has the value 14.
14 is greater than 11, so the top half of the list
(including the midpoint) is discarded.
The new highest position is 6.
Highest position (6) + lowest position (5) = 11
11/2 = 5.5, which rounds up to 6
Check at position 6.
The value held at position 6 is 11, a match. The
search ends.
A binary search in pseudocode might look like this:
A binary search is a much more
efficient algorithm than a linear search. In an
ordered list of every number from 0 to 100, a linear

search would take 99 steps to find the value 99. A
binary search would only require seven steps.
Another example of a computer
searching algorithm is binary search. This is a more
complex algorithm than linear search and requires
all items to be in order.
With each loop that is run, half of the data is
removed from the search. To do this, the algorithm
uses the index of items in the list - an index is the
number given to the position of an item in a list.
To determine the next item to be checked in a list,
the midpoint has to be identified. This is found by
adding the lowest index to the highest index and
dividing by two, then rounding either up or down to
the nearest integer if needed. Whether we round up
or down does not matter, as long as within a
particular search the same method is applied. For
example, if the highest index in a list is 8 and the
lowest is 0, the midpoint can be found using the
following sum:
Highest index (8) + lowest index (0) = 8
8/2 = 4
The algorithm runs as follows:
1. Start by setting the counter to the middle
position in the list.

2. If the value held there is a match, the search
ends.
3. If the value at the midpoint is less than the value
to be found, the list is divided in half, the lower
half of the list is ignored and the search keeps to
the upper half of the list.
4. Otherwise, if the value at the midpoint is greater
than the value to be found, the upper half of the
list is ignored and the search keeps to the lower
half of the list.
5. The search moves to the midpoint of the
remaining items. Steps 2 through 4 continue
until a match is made or there are no more items
to be found.
Binary search example
This algorithm could be used to search the following
list for the number 7:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
In a trace table, this would look like:
Search
term Start End Mid Found List
7 1 10 5 False [1, 2, 3, 4, 5, 6, 7,

Search
term Start End Mid Found List
8, 9, 10]
6 10 8 False [6, 7, 8, 9, 10]
6 7 6 False [6, 7]
7 7 7 True [7]
Comparing linear and binary searches
Although linear and binary searching produces the
same overall results, linear search is best used when
the data is not in order, or for smaller lists. However,
when the list is much longer and the data is in order,
it is far more efficient to calculate
the indexes needed to perform a binary search.
Linear v binary search example
Both algorithms could be used to search the
following list for the number 7:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Linear search would require eight steps to find the
search term in the list.

In a trace table, this would look like:
Linear search trace table
Search
term Index Data Found List
7 1 1 False [ 1 , 2, 3, 4, 5, 6, 7, 8,
9, 10]
2 2 False [1, 2 , 3, 4, 5, 6, 7, 8,
9, 10]
3 3 False [1, 2, 3 , 4, 5, 6, 7, 8,
9, 10]
4 4 False [1, 2, 3, 4 , 5, 6, 7, 8,
9, 10]
5 5 False [1, 2, 3, 4, 5 , 6, 7, 8,
9, 10]
6 6 False [1, 2, 3, 4, 5, 6 , 7, 8,
9, 10]
7 7 True [1, 2, 3, 4, 5, 6, 7 , 8,
9, 10]

In contrast, binary search would take just four steps
to find the same number.
In a trace table, this would look like:
Binary search trace table
Search
term Start Index Data Found List
7 1 10 5 False [1, 2, 3, 4, 5, 6, 7,
8, 9, 10]
6 10 8 False [6, 7, 8, 9, 10]
6 7 6 False [6, 7]
7 7 7 True [7]
Bubble sort
An example of a sorting algorithm is bubble sort.
This is a simple algorithm used for taking a list of
unordered numbers and putting them into the correct
order.
Each run through the list, from start to finish, is
known as a pass. The bubble sort continues until a
pass is made where no values have been swapped.
At this point, the list is sorted.

The algorithm runs as follows:
1. Look at the first number in the list.
2. Compare the current number with the next
number.
3. Is the next number smaller than the current
number? If so, swap the two numbers around. If
not, do not swap.
4. Move to the next number along in the list and
make this the current number.
5. Repeat from step 2 until the last number in the
list has been reached.
6. If any numbers were swapped, repeat again from
step 1.
7. If the end of the list is reached without any
swaps being made, then the list is ordered and
the algorithm can stop.

Linear seach and Binary seach

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish