Searching in Data Structure

Introduction of Searching in Data Structure

• Searching is an operation or a technique that helps to find the place of a given element or value in the list.

Definition of Searching

• Searching is an algorithmic process of finding out the specific and required information from a collection of data items stored as elements in some specific data structure format(such as an array, linked list, graph, or tree mainly.) in the computer memory. 

Characteristics of Searching

• A search operation is said to be successful or unsuccessful depending on whether the element being searched is found or not in the list.
• It can be applied to internal (such as stack and queue) and external data structures(Linked lists, trees, graphs).
• Sorting algorithms may require extra space for comparison and temporary storage of a few data elements.

Types of Searching

• There are the following types of searching:-

(I) Linear/Sequential/Simple Search :

• • It searches the data item in a sequential order i.e. the given value is compared (one by one from the beginning) with the element stored in the list. If the element is matched/found, it returns the value index, otherwise, it returns -1.
  • Examples are – Array, Linked List, etc.   
  • Advantages :
    • It is a basic and simplest searching algorithm.
    • It has a very simple implementation.
    • Sequential search is normally applied to the unsorted or unordered list.
    • Sequential search starts the finding data item from the beginning of the list (till the end, if the searched item is not found)and checks every element of the list.
  • Disadvantages :
    • They are effective in small-size lists or with fewer elements in the list.
    • A linear search scans/checks/compares one item at a time, without jumping to other items.
    • In linear search, the time taken to search the elements keeps increasing as the number of elements is increased.
    • It is a comparatively slow process.

(II) Binary/Half-Interval Search :

• • This searching technique looks for a specific/particular element by comparing the middlemost element of the collection or list i.e. Binary searching starts with sorted data structures by finding the middle element of the list. If the element is equal to the element that we are searching then return true/the index of the item is returned. If not equal and if the element is less than, then move to the right half part/sub-array of the list or if the element is greater than then move to the left half/sub-array of the list. This process is repeated, till the value is found or all mid-element data items are searched/compared/the size of the sub-array reduces to zero in the list.
  • This searching technique works on the principle of divide and conquer.
  • Advantages :
    • It is a comparatively fast searching algorithm because we basically ignore/leave half of the elements each time just after one comparison.
    • Binary search access/search data randomly.
    • It is useful when there are a large number of elements in a data structure.
  • Disadvantages :
    • Binary searching is only applied to a sorted data structure/array.
    • Not applied with simple or small data structure.

Advantages of Searching

• Takes less time to give information from a list/data structure.

Disadvantages of Searching

• Processing or Time consumed but when searching element not found in the list.

Use/Application of Searching

• Searching is a very important mechanism to find out specific data items from data storage quickly. Thus, searching provides effective and efficient processing of small as well as large amounts of stored data.