OBJECT Lab Session 03 Application of the Linear and binary search on a list of elements stored in an array. THEORY Linear Search A nonempty array DATA with N numerical values is given. This algorithm...

OBJECT

Lab Session 03

Application of the Linear and binary search on a list of elements stored in an array.

THEORY

Linear Search

A nonempty array DATA with N numerical values is given. This algorithm finds the location LOC and required value of elements of DATA. The variable K is used as a counter.

ALGORITHM

1. Set k := 1 & loc : = 0

1. Repeat step 3 & 4 while loc : = 0 &k < =="">


2. If (item = data[k]) loc : = k

Else

K = k + 1

1. If loc > = 0 or If (item = data[k]) then

Print “loc is the location of item”

Else

Print “no. not found”

1. Exit

Binary Search

Suppose DATA is an array that is sorted in increasing (or decreasing) numerical order or, equivalently, alphabetically. Then there is an extremely efficient searching algorithm, called binary search, which can be used to find the location LOC of a given ITEM of information in DATA.

The binary search algorithm applied to our array DATA works as follows: During each stage of our algorithm, our search for ITEM is reduced to a segment of elements of DATA: DATA[BEG], DATA[BEG+1], DATA[BEG+2], . . ., DATA[END]

Note that the variables BEG and END denote, respectively, the beginning and end locations of the segment under consideration. The algorithm compares ITEM with the middle element DATA[MID] of the segment, where MID is computed as:

MID = INT((BEG + END) / 2) (INT(A) refers to the integer value of A.)

If DATA[MID] = = ITEM, then the search is successful and we set LOC = MID.

Otherwise a new segment of DATA is obtained as follows:

1. If ITEM < data[mid],="" then="" item="" can="" appear="" only="" in="" the="" left="" half="" of="" the="" segment:="" data[beg],="" data[beg+1],="" .="" .="" .="" ,="">

So we reset END = MID –1 and begin searching again.

1. If ITEM > DATA[MID], then ITEM can appear only in the right half of the segment: DATA[MID+1], DATA[MID+2], . . . , DATA[END]

So we reset BEG = MID +1 and begin searching again.

Initially, we begin with the entire array DATA; i.e., we begin with BEG = 0 and END = N-1. If ITEM is not in DATA, then eventually we obtain BEG > END.

This condition signals that the search is unsuccessful, and in such a case we assign LOC = NULL. Here NULL is a value that lies outside the set of indices of DATA.

ALGORITHM

Algorithm: BINSEARCH(DATA, ITEM)

1. Set BEG = 0, END = N-1 and MID = INT((BEG + END) / 2)


2. Repeat steps 3 and 4 while BEG <= end="" and="" data[mid]="" !="">


3. If ITEM < data[mid],="" then="" set="" end="MID" –="" 1,="" else="" set="" beg="MID" +="">


4. MID = INT((BEG + END) / 2)


5. If DATA[MID] = ITEM, then Set LOC = MID Else Set LOC = NULL


6. Exit

LAB TASKS

1. Implement algorithms A1 and A2 in C/C++


2. Write a C/C++ program that makes use of the above implementations as a Your program should input the array from the user.


3. After implementation edit the code that shows after how many number of iteration searched value is found