Searching

Modern technology development has led to a vast amount of information available to the public. It is a fundamental ability to search through the bulky data sets over the Internet for specified piece of information. Various of topics related to searching will be discussed further.

Symbol Table

An abstract searching mechanism that a value entry is stored and later retrieved by a corresponding key is a symbol table, also known as dictionary. There are huge amount of keys and information for use in Internet and numerous applications such as symbol table in compiler design.

The main purpose of this data structure is to associate a value with a key and be able to search the value by its key. A formal definition of symbol table: a key-value pairs that supports two operations: Insert a pair into the table and Search for the value with a given key.

Technically, the keys are unique and duplicate keys may result in inconsistent searching operations. And values may collide with different associative keys such as two customers in a commercial database have the same DOB.

Note: a symbol table is a conceptual structure that supports the searching operation and it indicates dynamic key-value pairs during such operation; if searching for a customer's name given his ID, the ID is the key, if searching for the ID of a customer given the name, the name is the key.

Guidelines

Noting that the symbol table could have key-value pairs in which key equals the value; the searching operation would return either one, multiple or no results and this operation takes advantage of the principle of symbol table.

A plenty of data structures such as List, Array, Tree, Graph, Hash Table are built searching operation foundations. It is worth noted that List, often refers to LinkedList, is designed to have multiple containers of specific data objects connected to form a dynamic structure, while Array is a bulk of adjacent cells aligned in memory to form a static structure. (when locating ith element in Array structure, address(Array[i]) = address(Array[0]) + i * sizeof(Array object), thus it takes Ο(1) time)

Search Operations:

• SEARCH: find the specified element within the set of data.

• SELECT: locate the ith order statistic) within a possibly unordered set of data.

• MIN/MAX: find the minimum or maximum value among the values of the set of data.

• PREDECESSOR/SUCCESSOR: locate the immediate neighbors that are closest to the designated key in terms of values. PREDECESSOR(𝒳) is the maximal value closest to 𝒳 while SUCCESSOR(𝒳) is the minimal value closest to 𝒳.

• RANK: count the number of elements that are less than or equal to the specified key.

Comparison-based Searching

Searching Lower Bound

Table of Contents

• Hash Table - an associate array structure to assist in the processing of searching, insertion and deletion.

• Graph Search - graph searching primitives that are commonly used.

• Binary Search - searching _key_s by means of DnC principle.

• String Matching - searching characters or substrings in input strings, involving discussions of regular expression and KMP algorithm, etc.