Searching in Data Structure

Linear search, also known as sequential search, is a straightforward searching algorithm used to find a particular element in a list or array. The algorithm starts from the first element of the list and checks each element one by one until it either finds the target element or reaches the end of the list.

Algorithm - Linear search

LINEAR (DATA, N, ITEM, LOC)

Here, DATA is a linear array with N elements, and ITEM is the given element. This algorithm finds the location LOC of ITEM in DATA or sets LOC = 0 if the search is unsuccessful.

1. Insert ITEM at the end of DATA:
   Set DATA [N + 1] = ITEM
2. Initialise counter:
   Set LOC = 1
3. Search for ITEM:
   Repeat while DATA[LOC] ≠ ITEM:
   Set LOC = LOC + 1
   [End of loop] 
4. If LOC = N + 1, then set LOC = 0
5. EXIT 

Complexity of Linear Search Algorithm
The complexity is measured by the number of f(n) comparisons to locate ITEM in DATA, where DATA contains n elements. f(n) = n

Applications :
1) Works well on small or unsorted arrays/lists where sorting overhead is not worth it.
2) Due to low memory and limited processing power, linear search is ideal in embedded or real-time systems with very small data.

Limitations : 
1) Time-consuming as it checks each element one by one.
2) Compared to algorithms like binary search or hash-based lookups, linear search has O(n) time complexity, which is slow for large n.

Binary search is an efficient algorithm used to find the position of a target element (called ITEM) within a sorted array. It works by repeatedly dividing the search interval in half, hence the name "binary."  This method is much faster than linear search for large datasets

Algorithm for Binary Search

(Binary Search) BINARY[DATA, LB, UB , ITEM, LOC]

Here, DATA is a sorted array with a lower bound, LB, and an upper bound. DB and ITEM are given an item of information. The variables BEG, END, and MID denote, respectively, the beginning, end, and middle location of a segment of elements of DATA. This algorithm finds the location LOC of ITEM in DATA or sets LOC=NULL 

           1. [Initialize segment variables.] 
Set BEG := LB, END := UB and MID = INT [(BEG+END)/2] 
           2. Repeat steps 3 and 4 while BEG <= END and DATA [MID] `\cancel(=)`  ITEM 
           3. IF ITEM < DATA [MID], then:
Set END := MID-1 
                   Else: 
Set BEG := MID + 1 
                   [End of IF structure] 
           Set MID:=INT [(BEG+END)/2] 
                   [End of step 2 loop J ]
                   If data [MID] = ITEM, then : 
Set LOC := MID 
                   Else: 
Set LOC: =NULL 
                  [End of IF structure] 
           4. Exit

Complexity of Binary Search Algorithm 
The complexity is measured by the number of f(n) comparisons to locate ITEM in DATA, where DATA contains n elements. f (n) = [log₂ n] +1

Applications: 
(1) This algorithm is used to search for an order in an array. 
(2) To find out the target element, whether it is present or not. If present, then correspondingly give the position in the array.

Limitations: 
(1) The given list must be sorted. 
(2) The access of a list must be random, meaning the middle element can be accessed.