Algorithms & Data Structures - Searching

Searching
√The process used to find the location of a target among the list of object.
√We begin with list searching and a discussion of two basic search algorithm

List Searches
√The two basic searches for arrays are the sequential search and the binary search.

Sequential Search
√The sequencial search is used whenever the list is not ordered.
√It is useful for small lists or lists that are not searched often.
√In sequential search, we start searching for the target at the beginning of the list and continue until we find the target or we are sure that it is not in the list.
√The efficiency of sequential search is O(n).










Binary Search
√The binary search starts by testing the data in the element at the middle of the array to determine if the target is in the first or the second half of the list.
√If it is in the first half, we do not need to check the second half.
√If it is in the second half, we do not need to check the first half.
√To find the middle of the list, we need 3 variables: one to identify the beginning of the list, one to identify the middle of the list and one to identify the end of the list.
√The formula to calculate the mid is:
   Mid = [(begin + end ) / 2 ]
√The efficiency of the binary search is O(log n).









Binary Search Tree
√The array structure provides a very efficient search algorithm, but its insertion and deletion algorithms are very inefficient.
√The binary search tree and AVL tree (chapter 3)provides a very efficient search and at the same time efficient insertion and deletion algorithm.

Basic Concepts
A binary search tree is a binary tree with the following properties:
√All items in the left subtree are less than the root.
√All items in the right subtree are greater than or equal to the root.
√Each subtree is itself a binary search tree.