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



 Given an array
arr
ofn
elements and a target valuex
.
 Given an array





 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
).
 Iterate through the array of elements starting from the first element (index


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.
 Disadvantages :
 They are effective in smallsize 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.

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/SelfOrganizing 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
ofn
elements and a target/search valuex
, start from the beginning of the array.
 Given an 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
andi
is greater than0
: Swap the element with the element at the position
i1
(the previous element).  This moves the found element one position closer/earlier to the front of the array.
 Swap the element with the element at the position
 If the element is not found after iterating through the entire array, return an indicator (e.g.,
1
).
 Iterate through the array of elements starting from the index


Step3:Termination



 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.

 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 index2
.  The elements in positions
2
and1
are swapped, so the array becomes[4, 3, 2, 5, 1]
.  Hence, the returned index is
1
, the new position of the element3
.
 Searching for


(III) Binary/HalfInterval 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/subarray of the list or if the component is greater than then move to the left half/subarray of the list. This process is repeated, till the value is found or all midelement data items are searched/compared/the size of the subarray 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
ofn
elements and a target/search valuex
, initialize two pointers:low
to the first element (index0
) andhigh
to the last element (indexn1
).
 Given a sorted array say


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 valuex
: If
arr[mid]
is equal tox
, returnmid
and break showing the target value found.  If
arr[mid]
is less thanx
, adjust thelow
pointer tomid + 1
(search in the right half of the divided list).  If
arr[mid]
is greater thanx
, adjust thehigh
pointer tomid  1
(search in the left half of the divided list).
 If
 Repeat the process until
low
exceedshigh
.
 Calculate the middle index


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
(element5
).  Since
5
is less than7
, adjustlow
to5
.  Calculate the new middle index:
mid = 7
(element8
).  Since
8
is greater than7
, adjusthigh
to6
.  Calculate the new middle index:
mid = 5
(element6
).  Since
6
is less than7
, adjustlow
to6
.  Calculate the new middle index:
mid = 6
(element7
).  Since
7
is equal to7
, return6
.
 Calculate the middle index:
 Searching for


 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(logn)$.
 Worst Case: $O(logn)$.
Binary search is much more efficient than linear search for large datasets due to its logarithmic time complexity.
 Advantages
(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.


Working Mechanism of Interpolation Search

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)$$




 Here,
low
is the starting index,high
is the ending index,key
is the value to be searched, andarr
is the sorted array.
 Here,

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, updatehigh
topos  1
.  If the value at
arr[pos]
is less than the key, updatelow
topos + 1
.
 If the value at

Finally, repeat:
 Repeat the process until the key is found or the subarray reduces to zero size (
low
becomes greater thanhigh
).
 Repeat the process until the key is found or the subarray reduces to zero size (


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 is18
.

Step1 : Initial Setup



low = 0
,high = 14
(array length – 1), searchingkey 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 than18
, updatelow
to4 (pos + 1)
.
 Since


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
.
 Return the position


Time Complexity:
 Best case: $O(1)$
 Average case: $O(g (gn))$ 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.
0 Comments