Searching: Linear Search and Binary Search Techniques

SEARCH OPERATION:

Searching generally refers to the process of obtaining the index location i.e LOC of a REQUESTED VALUE in an array or any other data structure. The search operation is said to be successful if REQUESTED VALUE appears in the array & unsuccessful otherwise. We here have two types of searching techniques discussed here :

• Linear Search
• Binary Search

LINEAR SEARCH:

Suppose DATASET we use for an algorithm is a linear sequence with n elements. No other information about DATASET is available, the most spontaneous(naive “pronounced as na-ive”) and brute force approach order to search for a given VALUE in DATASET is to compare  VALUE with each element of DATASET one by one. First, we need to test whether DATASET[1]=VALUE, and then we test whether DATASET[2] =VALUE and so on. This method which traverses DATA sequentially to locate ITEM is called linear search or sequential search.

Algorithm :

LINEAR (DATA, N, ITEM, LOC)   

Step 1: [Insert ITEM at the end of data]

Set DATA [N+1] = ITEM

Step 2: [Initialize counter]

Set LOC=1

Step 3: [Search for ITEM]

Repeat while DATA [LOC]!= ITEM

Step 4: [Successful]

If LOC=N+1

Then Set LOC = 0

Step 5: Exit

The complexity of Linear Search Algorithm: The complexity of this search algorithm is measured by the number of functions f(n) of comparisons required to find VALUE in DATASET where DATASET contains n elements.

There are two important cases to consider: the average case and the worst cases. 

The worst-case occurs when one may search through the entire sequence of DATASET. In this case, the algorithm requires F(n)= n+1 comparisons. Thus, it is justified that in the worst case, running time is proportional to n(size of sequence). 

The average case running time uses the probabilistic notion of expectation. The probability that VALUE appears in DATASET[K] and q is the probability that VALUE does not appear in DATASET. Since the algorithm uses k comparisons when VALUE appears in DATASET[K], the average number of comparisons is given by F(n) = 1. p1 + 2. p2 +…..+ n.pn + (n+1).q.

BINARY SEARCH:

Suppose DATASET is an array that is sorted in increasing numerical order. Then there is an extremely efficient searching algorithm, called binary search.

Algorithm :

Binary search (DATA, LB, UB, ITEM, LOC)

Step 1: [Initialize the segment variables]

Set BEG := LB, END := UB and MID := INT ((BEG + END)/2)

Step 2: [Loop]

Repeat Step 3 and Step 4 while BEG <= END and DATA [MID] != ITEM

Step 3: [Compare]

If ITEM < DATA [MID]

then set END := MID - 1

Else

Set BEG = MID + 1

Step 4: [Calculate MID]

Set MID := INT ((BEG + END)/2)

Step 5: [Successful search]

If DATA [MID] = ITEM

then set LOC := MID

Else set LOC := NULL

Step 6: Exit

The time complexity of the Binary Search Algorithm: The complexity is measured by the number of functions f(n) of comparison to locate VALUE in DATASET where DATASET contains n elements. Observe that each comparison reduces the sample size in half of its size in the past. Hence we require at most f(n) comparisons to locate VALUE where 2f(n) > n Or equivalently F(n) = [log2 n] + 1.

The running time for the worst case is approximately equal to log2 n and the average case is approximately equal to the running time for the worst case.