Chapter 2. Search Algorithm
Recommended Reading: 【Algorithm】 Algorithm Table of Contents
1. Overview
a. Search Algorithm Experiment
1. Overview
⑴ Search
① Given an array C = ｛a1, a2, ···, an｝and a key e, the process of finding ai where ai = e
② The very first element that satisfies the above condition
③ Or , the very last element that satisfies the above condition
④ Or , all elements that satisfy the above condition
⑵ The array C can be either a sorted array or an unsorted array
① Linear search: O(N)
② Binary search: O(log2 N)
③ One search after sorting: O(N log2 N) + O(log2 N) = O(N log2 N)
④ N searches after sorting: O(N log2 N) + N × O(log2 N) = O(N log2 N)
⑤ N searches on a sorted array: N × O(log2 N) = O(N log2 N)
⑶ Types
① Type 1. Depth-First Search (DFS)
○ Stack-based
○ Memory usage: O(D) or O(D × B) (where D = max depth, B = branching factor)
○ Does not always find the shortest path
depth_first(value):
do_I_match_value?
depth_first(children)
② Type 2. Breadth-First Search (BFS)
○ Queue-based
○ Memory usage: O(BD) (where D = max depth, B = branching factor)
○ Always finds the shortest path
breadth_first(value):
queue = [root node]
for each item in queue:
do_I_match_value?
append all children to queue
2. Linear Search
⑴ Overview
① A method of checking each element one by one to see if a specific element exists
② Can be used on both sorted and unsorted arrays
③ Time complexity
⑵ Algorithm (Python)
① Linear search algorithm that returns whether the element is found
def linear_search (l, e):
found = False
for i in l:
if(i == e):
found = True
return found
② Linear search algorithm that returns the position of the found element
def linear_search_idx (l, e):
n = len(l)
idx = -1
for i in range(n):
if(l[i] == e):
idx = i
return idx
③ Linear search algorithm for a sorted array
def linear_search_sorted (l, e):
found = False
for i in l:
if(l[i] == e):
found = True
break
if(i > e):
found = False
break
return found
3. Binary Search
⑴ Overview
① Binary search requires a sorted array
⑵ Binary Tree
① Definition: A tree consisting of nodes with a degree of 2 or less, meaning nodes can have at most two children
② The maximum number of nodes at level i of a binary tree is 2i-1
③ Type 1. Full Binary Tree: A completely filled tree
④ Type 2. Complete Binary Tree: A tree where only the last leaf is not fully filled
⑤ Type 3. Skewed Binary Tree: A special binary tree where nodes have only left or right children
⑶ Search Principle
Given a sequence like 4, 6, 5, 3, 7, 2, let’s build a binary tree as follows.
First, 4 is attached as the root. Then 6 is greater than 4, so it attaches to the right of 4. Next, 5 is greater than 4, so it follows the direction of 6, but since it is smaller than 6, it attaches to the left of 6. The tree is built in this way. Regarding the names of each node, the node closer to the root among two directly connected nodes is called the parent node, and the farther one from the root is called the sibling node. Also, sibling nodes are divided into left sibling nodes and right sibling nodes. Furthermore, if there is a path from one node to another, the former is called the ancestor node, and the latter is called the descendant node.
Expressing each node in the binary tree in binary makes it easier to perform various operations. Each substitute value is defined as follows:
Then 4 becomes 1, 3 becomes 10, 6 becomes 11, and 5 becomes 110.
The process of finding a specific value in a binary tree is called binary tree search or binary tree traversal. Binary tree search has four types: First, in-order traversal searches in the order of left, center, and right, resulting in 2-3-4-5-6-7. When the order of the nodes being searched is output, the node values in the tree are sorted. Second, level-order traversal searches nodes in order of smallest level (shortest distance from root) and follows the order 4-3-6-2-5-7. Third, pre-order traversal searches in the order of center, left, and right, resulting in 4-3-2-6-5-7. Lastly, post-order traversal searches in the order of left, right, and center, resulting in 2-3-5-7-6-4. Binary tree search is typically implemented using a recursive function. For example, in-order traversal can be implemented as f(4) = f(3) + 4 + f(6).
Now let me introduce the level-ancestor (LA) operation. LA(x, k) represents the value of the ancestor node at level k of the node with value x. For example, LA(2, 1) = 3, and LA(5, 3) = -1. Here, -1 is an exceptional value that always appears when you specify a higher level than the given node. This operation can be easily calculated using substitute values.
The log value here is the number of digits of the substitute value of x - 1. This value can be easily calculated.
Another operation is the lowest-common-ancestor (LCA). LCA(x, y) represents the value of the closest common ancestor node (i.e., the node with the highest level) of the nodes with values x and y. For example, LCA(5, 7) = 6, and LCA(2, 6) = 4. This can also be calculated using substitute values.
There are also various other operations, which can also be calculated using substitute values. This shows how creative methodologies can significantly simplify complex problems.
⑷ Algorithm (Python)
① Algorithm using recursion
def binary_search (l, e):
def bs(l, low, high, e):
if(low > high):
return -1
i = int((low+high)/2)
if(l[i] == e):
return i
elif (l[i] < e):
i = bs(l, i+1, high, e)
else:
i = bs(l, low, i-1, e)
return i
return bs(l, 0, len(l)-1, e)
② Algorithm using iteration
def binary_search_iter (l, e):
low = 0
high = len(l) - 1
while(low < high):
i = int((high + low) / 2)
if(l[i] == e):
return i
elif(l[i] < e):
low = i + 1
else:
high = i-1
return -1;
4. Other Search Algorithms
⑴ Type 1. Elastic Search: A natural language search algorithm used by Google
Input: 2016.09.18 21:47