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 Repeat step 3 & 4 while loc : = 0 &k < = n If (item = data[k]) loc : = k Else K = k + 1 If loc > = 0 or If (item = data[k]) then Print “loc is the location of item” Else Print “no. not found” 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: If ITEM < DATA[MID], then ITEM can appear only in the left half of the segment: DATA[BEG], DATA[BEG+1], . . . , DATA[MID-1] So we reset END = MID –1 and begin searching again. 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) Set BEG = 0, END = N-1 and MID = INT((BEG + END) / 2) Repeat steps 3 and 4 while BEG <= END AND DATA[MID] != ITEM If ITEM < DATA[MID], then Set END = MID – 1, Else Set BEG = MID + 1 MID = INT((BEG + END) / 2) If DATA[MID] = ITEM, then Set LOC = MID Else Set LOC = NULL Exit LAB TASKS Implement algorithms A1 and A2 in C/C++ Write a C/C++ program that makes use of the above implementations as a Your program should input the array from the user. After implementation edit the code that shows after how many number of iteration searched value is found NOTE: LAB TASK 1 ANSWER IS REQUIRED ONLY

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 Repeat step 3 & 4 while loc : = 0 &k < = n If (item = data[k]) loc : = k Else K = k + 1 If loc > = 0 or If (item = data[k]) then Print “loc is the location of item” Else Print “no. not found” 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: If ITEM < DATA[MID], then ITEM can appear only in the left half of the segment: DATA[BEG], DATA[BEG+1], . . . , DATA[MID-1] So we reset END = MID –1 and begin searching again. 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) Set BEG = 0, END = N-1 and MID = INT((BEG + END) / 2) Repeat steps 3 and 4 while BEG <= END AND DATA[MID] != ITEM If ITEM < DATA[MID], then Set END = MID – 1, Else Set BEG = MID + 1 MID = INT((BEG + END) / 2) If DATA[MID] = ITEM, then Set LOC = MID Else Set LOC = NULL Exit LAB TASKS Implement algorithms A1 and A2 in C/C++ Write a C/C++ program that makes use of the above implementations as a Your program should input the array from the user. After implementation edit the code that shows after how many number of iteration searched value is found NOTE: LAB TASK 1 ANSWER IS REQUIRED ONLY

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

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

Repeat step 3 & 4 while loc : = 0 &k < = n
If (item = data[k]) loc : = k

Else

K = k + 1

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

Print “loc is the location of item”

Else

Print “no. not found”

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:

If ITEM < DATA[MID], then ITEM can appear only in the left half of the segment: DATA[BEG], DATA[BEG+1], . . . , DATA[MID-1]

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

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)

Set BEG = 0, END = N-1 and MID = INT((BEG + END) / 2)
Repeat steps 3 and 4 while BEG <= END AND DATA[MID] != ITEM
If ITEM < DATA[MID], then Set END = MID – 1, Else Set BEG = MID + 1
MID = INT((BEG + END) / 2)
If DATA[MID] = ITEM, then Set LOC = MID Else Set LOC = NULL
Exit

LAB TASKS

Implement algorithms A1 and A2 in C/C++
Write a C/C++ program that makes use of the above implementations as a Your program should input the array from the user.
After implementation edit the code that shows after how many number of iteration searched value is found

NOTE: LAB TASK 1 ANSWER IS REQUIRED ONLY

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.