Searching

7.1 Introduction
Searching is used to find the location where element is available or not. There are two types of searching techniques as given below :
1. Linear or sequential searching
2. Binary searching


Experiment 22

Aim –Write a program to search the given element using linear search.

Theory
In linear search, we access each element of an array one by one sequentially and see whether it is desired element or not. A search will be unsuccessful if all the elements are accessed and the desired element is not found. In the worst case the number of average case we may have to scan half of the size of the array. Therefore, linear search can be defined as a technique which traverses the array sequentially to locate the given item.
The time taken or the number of comparisons made in searching a record in search table determines the efficiency of the technique. If the desired record is present in the first position then only one comparison is made. If the desired record is last one then n comparisons have to made.


Algorithms
Let A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in A, or sets LOC=0 if the search is unsuccessful.

1. [Initialize counter]
set LOC = 1
2. [Serach for item]
repeat while A[LOC] != ITEM
set LOC=LOC+1
3.[Successful]
if LOC = N+1, then
set LOC=0
4. Exit.



Experiment 23

Aim –Write a program to search the given element using binary search.

Theory- The search technique searches the given item in minimum possible comparisons. To do the Binary search, first the array is sorted. The logic behind the technique is
1. First find the middle element of the array.
2. Compare the mid element with the item
3. There are three cases:
a. If it is the desired element search is successful.
b. If it is less than desired item, then search the first half of the array
c. If it is greater than desired item, then search the second half of the array
Repeat the same steps until the search is exhausted.


Algorithms
Let A is sorted array with lower bound LB and upper bound UB, and ITEM is a given ITEM of information. The variables BEG, END and MID denoted, respectively, the beginning, end and middle location of a segment of element of A. This algorithm finds the location LOC of ITEM in A 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 A[MID] != ITEM
3. if ITEM < A [MID] , then
Set END = MID – 1
Else
Set BEG = MID +1
[end of if structure]
4. set mid = int ((BEG + END))/2
[End of step 2 loop]
5. if A[MID] = ITEM then
set LOC = MID
else
set LOC = NULL
[end of if structure]
6.exit


7.2 Viva voice

1.What is sorting? List different types of sorting techniques.
2. What are the factors to be considered during the selection of sorting technique.
3.Which of the following sorts will take longest time to execute and which will take the shortest time?
a) Merge sort
b) Heap sort
c) Selection sort
d) Shell sort
e) Quick sort
f) Insertion sort

4. How many comparisons are required to sort an array of 10 elements using selection sort , if the original array values already sorted?
5. What do you mean by efficiency of the algorithm?
6. What is the best case , average case and worst case complexity of following:
a) merge sort
b) heap sort
c) selection sort
d) shell sort
e) quick sort
f) insertion sort
7.What are the factors on which complexity of algorithm depends? Which factor is taken into consideration while determining the complexity of algorithm for searching and sorting?
8.Suppose name consist of following list of names with n= 5
Amit, jaswinder , chander, gagan, seema
Find the number of comparisons to sort name using radix sort.
9.What is searching?
10.Distinguish between the following
a) Internal search and external search
b) Primary key and secondary key
c) Internal key and external key
10. Which is efficient search technique?
11. What is hashing? What is the need for a hashing?
12. What is the need for an ordered table searching?
13. What are the techniques to resolve hash clashes?