Searching
Searching is the process of finding the location of a given element in a set of elements. The search is said to be successful if the given element is found i.e., the element does exist in the collection (such as an array); otherwise it is unsuccessful.
Two simple approaches to searching are:
- Linear search: This method traverses a list sequentially to locate the search key.
- Binary search: This method works on sorted lists by progressively making better guesses to find the location of a search key.
|
|
- Traversing and Searching a Linear Linked List
Traversing a list A linear list can be traversed in two ways In order traversal Reverse order traversal In order Traversal To traverse the linear linked list, we walk the list using the pointers, and process each element until we reach the last element. .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; [...]...
- Binary Tree – Searching a Node
An element in a binary search tree can be searched very quickly. A search operation on binary tree is similar to applying binary search technique to a sorted linear array. The element to be searched will be first compared with root node. If it matches with the root node then the search terminates. Otherwise search [...]...
- Linear Search
This method traverses a list sequentially to locate the search key. The algorithm that one chooses generally depends on the organization of the array elements. If the elements are in random order, then one should choose the linear search technique. Algorithm linearsearch (a,n,item,loc) Here "a" is an array of the size n. This algorithm finds [...]...
- Binary Search
This method works on sorted lists by progressively making better guesses to find the location of a search key. Illustration Consider the following array: 3 10 15 20 35 40 60 Suppose we want to search the element "15" We take beg = 0, end = 6 and compute the location of the middle element [...]...
- Insertion in a Linear Linked List
To insert an element in the list, the first task is to create a new node, assign the element to be inserted to the info field of the node, and then place the new node at the appropriate position by adjusting the appropriate pointers. Insertion in the list can take place at the following positions: [...]...