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/Simple Search :

• • Linear search is a simple search algorithm used to find the position of a target/search value within a list.
  • It checks each element of the list sequentially until the target value is found or the list is exhausted.
  • Linear search is easy to implement and works on both sorted and unsorted lists.
  • 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.
  • Linear search is suitable when:-
    • The list is small.
    • The list is unsorted, and the overhead of sorting is not justified.
    • The simplicity of implementation is a priority.
    • The cost of more complex search algorithms is not warranted due to infrequent searches.
  • Examples are – Array, Linked List, etc.   
  • Working Mechanism Algorithms of Linear Search

• 1. • • Iterate through the array of elements starting from the first element (index 0).
       • For each element, check if it is equal to x.
       • If an element is found to be equal to x, return its index.
       • If the end of the array is reached and the target value is not found, return an indicator (e.g., -1).
  2. 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.
     • Simple and easy to implement.
     • No requirement for the list to be sorted.
  3. Disadvantages :
     • They are effective in small-size lists or with fewer elements in the list i.e. inefficient for large lists compared to more advanced search algorithms like binary search.
     • 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.

  4. Complexity

     • Best Case: $O(1)$ (when the element is at the first position).
     • Average Case: $O(n)$ (linear search).
     • Worst Case: $O(n)$ (when the element is at the last position or not present).

(II) Transpose Sequential Search/Self-Organizing List :

• • Transpose Sequential Search is a variant of the linear search algorithm that improves the efficiency of subsequent searches by rearranging the elements of the list each time a search is performed. When an element is found, it is swapped with the previous element in the list.
  • This approach exploits the principle of locality, assuming that elements that are searched for more frequently are likely to be searched for again soon.

  • Transpose Sequential Search is useful when:

    • The list is not sorted.
    • Some elements are accessed more frequently than others.
    • We want to optimize for repeated searches where the access pattern shows some locality (recently accessed elements are likely to be accessed again soon).
  • This search method is less beneficial if each search query is independent and uniformly distributed across the elements, as the transpositions would not significantly change the search times.

  • Complexity

    • Best Case : $O(1)$ (when the element is at the first position).
    • Average Case : $O(n)$ (linear search).
    • Worst Case : $O(n)$ (when the element is at the last position or not present).

    However, for repeated searches, the average search time can improve due to the transposition of frequently accessed elements.

  • Working Mechanism Algorithm of Transpose Sequential Search 

Setp1: Initial Setup

• • • • Given an array arr of n elements and a target/search value x, start from the beginning of the array.

Setp2: Search Loop

• • • • Iterate through the array of elements starting from the index 0.
      • For each element, check if it is equal to x.
      • If the element is found at position i and i is greater than 0:
        • Swap the element with the element at the position i-1 (the previous element).
        • This moves the found element one position closer/earlier to the front of the array.
      • If the element is not found after iterating through the entire array, return an indicator (e.g., -1).

Step3:Termination

• 1. • • If the target value is found, return the index where it was found (or its new index after swapping).
       • If the target value is not found, return -1 to signify that the value is not present in the array.
  2. For Example 

Suppose we have an array [4, 2, 3, 5, 1] and using Transpose Sequential Search, we have

• • • • Searching for 3 will find it at the index 2.
      • The elements in positions 2 and 1 are swapped, so the array becomes [4, 3, 2, 5, 1].
      • Hence, the returned index is 1, the new position of the element 3.

(III) 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 component 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 component is less than, then move to the right half part/sub-array of the list or if the component 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.
  • Binary search can also be implemented recursively.
  • Binary search is suitable when:-
    • The list is sorted.
    • Fast search times are required.
    • The overhead of sorting (if the list is not already sorted) is justified by the number of searches to be performed.

  • Working Mechanism/Algorithm of Binary Search

Step 1: Initial Setup

• • • • Given a sorted array say arr of n elements and a target/search value x, initialize two pointers: low to the first element (index 0) and high to the last element (index n-1).

Step 2: Search Loop

• • • • Calculate the middle index mid using the formula:-
             mid = low + (high - low)/2
      • Compare the middle element arr[mid] with the target value x:
        • If arr[mid] is equal to x, return mid and break showing the target value found.
        • If arr[mid] is less than x, adjust the low pointer to mid + 1 (search in the right half of the divided list).
        • If arr[mid] is greater than x, adjust the high pointer to mid - 1 (search in the left half of the divided list).
      • Repeat the process until low exceeds high.

Step 3: Termination

• • • • If the target value is found, return its index.
      • If the search range is exhausted and the target value is not found, return an indicator (e.g., -1).
  • Examples

Given the sorted array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

• • • Searching for 7 will:
      • Calculate the middle index: mid = 4 (element 5).
      • Since 5 is less than 7, adjust low to 5.
      • Calculate the new middle index: mid = 7 (element 8).
      • Since 8 is greater than 7, adjust high to 6.
      • Calculate the new middle index: mid = 5 (element 6).
      • Since 6 is less than 7, adjust low to 6.
      • Calculate the new middle index: mid = 6 (element 7).
      • Since 7 is equal to 7, return 6.

• • Advantages
    • It is a comparatively much faster than linear search for large datasets because we 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.
    • Much faster than a linear search for large datasets.
  • Disadvantages
    • Binary searching is only applied to a sorted data structure/array.
    • Not applied with simple or small data structure.
    • More complex to implement compared to linear search.
  • Complexity
    • Best Case: $O(1)$ (when the element is at the middle position in the first comparison).
    • Average Case: $O(\log n)$.
    • Worst Case: $O(\log n)$.
    Binary search is much more efficient than linear search for large datasets due to its logarithmic time complexity.

(IV) Interpolation Search :

• • Interpolation search is an algorithm used for searching for a given key value in a sorted array.
  • This search algorithm uses an interpolation formula to estimate the position of the target/search key value in a sorted array or list.
  • This algorithm makes a more intelligent guess based on the uniform distribution of the data i.e. it works on uniformly distributed data (the interval between the elements should be uniform i.e. does not have a large difference).
  • The algorithm estimates the position of the search key value in the array based on the value of the key and the values at the endpoints of the array not as midpoint value as in binary search.
  • It uses a formulaic approach to determine the position of the target element within the array.
  • It is most effective when:
    • The array is sorted.
    • The data is uniformly distributed.
    • Frequent searches on static datasets where preprocessing (sorting) is feasible.

  • Interpolation search provides a performance advantage over binary search in cases where the data is uniformly distributed, offering a faster search time on average.

  • Working Mechanism of Interpolation Search 

    1. First Calculate the Probe Position(pos) using the Interpolation formula:

       • The probe position is calculated using the formula: $$\text{pos}=\text{low}+\left(\frac{(\text{key}-\text{arr}[\text{low}])\times (\text{high}-\text{low})}{\text{arr}[\text{high}]-\text{arr}[\text{low}]}\right)$$

• • 1. • Here, low is the starting index, high is the ending index, key is the value to be searched, and arr is the sorted array.

    2. Check and Verify the Rules:

       • If the value at arr[pos] is equal to the key, the search is successful.
       • If the value at arr[pos] is greater than the key, update high to pos - 1.
       • If the value at arr[pos] is less than the key, update low to pos + 1.

    3. Finally, repeat:

       • Repeat the process until the key is found or the subarray reduces to zero size (low becomes greater than high).

  • For Example

    Consider an example with the sorted array arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] and the search key value is 18.

Step1 : Initial Setup

• • • • low = 0, high = 14 (array length – 1), searching key value = 18

Step2 : First Probe Position

pos = 0 +[(18 – 10) x (14 – 0) / (47 – 10)] = 0 + [(8×14)/37] = 0+(112/37) =3.027

Thus, the key value at arr[3] is 16.

Step3 : Adjust low using the Rules

• • • • Since 16 is less than 18, update low to 4 (pos + 1).

Step4 : Second Probe Position

pos = 4 + [(18 – 18) x (14 – 4)] = 4+(0) = 4 

Value at arr[4] is 18, which is the key.

Step5 : Key Found

• • • • Return the position 4.

  • Time Complexity:

    • Best case: $O(1)$
    • Average case: O(log (log n)) for uniformly distributed data.
    • Worst case: $O(n)$ when data distribution is highly skewed.

  • Space Complexity: $O(1)$

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.