Linear Search
It begins by comparing x and a1.
When x = a1, the solution is the location of a1.
When x ≠ a1, compare x with a2. If x = a2, the solution is the location of a2.
Continue this process, comparing x successively with each term of the list until a match is found, where the solution is the location of that term unless no match occurs.
This algorithm is also called the sequential search.
# Pseudocode
x: target integer
a1, a2, ... , an: distint integers stored in an array
location: index of x found in the array
procedure()
i := 1
while (i is less than or equal to n) and (x is not equivalent to ai) do:
i := i + 1
/* if x is found */
if i is less than or equal to n
location := i
/* if x is not found */
else
location := 0
return location
Binary Search
It proceeds by comparing the element to be located to the middle term of the list.
The list is split into two smaller sublists of the same size, or where one of them has one fewer term than the other.
The middle term of the list is floor(n / 2), where n is the number of the elements in the list.
Binary Search is much more efficient than Linear Search.
Note that, however, Binary Search can be used when the list has terms occurring in order of increasing size!
# Example
Search for 19 in the following list
[ 1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22 ];
- Split this list into two smaller lists with eight terms each:
list_left = [ 1, 2, 3, 5, 6, 7, 8, 10 ]
list_right = [ 12, 13, 15, 16, 18, 19, 20, 22 ] - Largest term in list_left: 10
10 < 19, so the search for 19 can be restricted to the list containing the 9th through the 16th terms of the original list. - Split list_right:
list_left = [ 12, 13, 15, 16 ]
list_right = [ 18, 19, 20, 22 ] - Largest term in list_left: 16
16 < 19, so list_right can be considered only. - Split list_right:
list_left = [ 18, 19 ]
list_right = [ 20, 22 ] - Because 19 of list_list is not greater than the target value 19, the search is restricted to list_left
- Split list_left:
list_left = [ 18 ]
list_right = [ 19 ] - 18 < 19, so the search is restricted to list_right.
- Now the search has been narrowed down to one term and 19 is located as the 14th term in the original list.
# Pseudocode
arr: array
x: target integer
a1, a2, ... , an: increasing intergers stored in an array
m: midpoint
procedure()
i := 1
j := arr.size()
while i is less than j do:
m := floor((i + j) / 2)
if x is greater than am
i := m + 1
else
j := m
end while
/* if x is found */
if x is equal to ai
location := i
/* if x is not found */
else
location := 0
return location'Algorithms' 카테고리의 다른 글
| Halting Problem 정지 문제 (0) | 2021.08.24 |
|---|---|
| Greedy Algorithm 그리디(탐욕) 알고리즘 (0) | 2021.08.24 |
| [Sorting] Selection Sort 선택정렬 (0) | 2021.08.24 |
| [Sorting] Insertion Sort 삽입정렬 (0) | 2021.08.24 |
| [Sorting] Bubble Sort 버블정렬 (0) | 2021.08.24 |
