One Stop GATE Forum: Searhing techniques

Message

Searching Tehniques

2.2 Searching

Let us assume that we have a sequential file and we wish to
retrieve an element matching with key ‘k’, then, we have to search the
entire file from the beginning till the end to check whether the
element matching k is present in the file or not.

There
are a number of complex searching algorithms to serve the purpose of
searching. The linear search and binary search methods are relatively
straight forward methods of searching.

2.2.1 Sequential search

In this method, we start to search from the beginning of the
list and examine each element till the end of the list. If the desired
element is found we stop the search and return the index of that
element. If the item is not found and the list is exhausted the search
returns a zero value.

In the worst case the item is not found or the search item is the last (n^th)
element. For both situations we must examine all n elements of the
array so the order of magnitude or complexity of the sequential search
is n. i.e., O(n). The execution time for this algorithm is proportional
to n that is the algorithm executes in linear time.

The algorithm for sequential search is as follows,

Algorithm : sequential search
Input : A, vector of n elements
              K, search element
Output : j –index of k
Method : i=1
	     While(i<=n)	
	           {
		    if(A=k)
		       {
			write("search successful")
			write(k is at location i)
			exit();
		       }
		  else
                                 i++
                           if end
                  while end
                          write (search unsuccessful);
            algorithm ends. 

2.2.2 Binary search  

Binary search method is also relatively simple method. For this
method it is necessary to have the vector in an alphabetical or
numerically increasing order. A search for a particular item with X
resembles the search for a word in the dictionary. The approximate mid
entry is located and its key value is examined. If the mid value is
greater than X, then the list is chopped off at the (mid-1)^th
location. Now the list gets reduced to half the original list. The
middle entry of the left-reduced list is examined in a similar manner.
This procedure is repeated until the item is found or the list has no
more elements. On the other hand, if the mid value is lesser than X,
then the list is chopped off at (mid+1)^th location. The
middle entry of the right-reduced list is examined and the procedure is
continued until desired key is found or the search interval is
exhausted.

The algorithm for binary search is as follows,

Algorithm : binary search
Input : A, vector of n elements
              K, search element
Output : low –index of k
Method : low=1,high=n
	     While(low<=high-1)	
	           {
		    mid=(low+high)/2
		       if(k<a[mid])
                                    high=mid
                               else
                                    low=mid
                               if end
                         }
                       while end	
                       if(k=A[low])
                             {
                                write("search successful")
		        write(k is at location low)
			exit();

		       }
		  else
                                write (search unsuccessful);
                      if end;     
            algorithm ends.

click here for more details:

http://www.vyomworld.com/gate/cs/ada/2.2.asp

Author	Message
sumana Newbie Joined: 08Apr2007 Online Status: Offline Posts: 9	Topic: Searhing techniques Posted: 08Apr2007 at 9:59pm
	Searching Tehniques 2.2 Searching Let us assume that we have a sequential file and we wish to retrieve an element matching with key ‘k’, then, we have to search the entire file from the beginning till the end to check whether the element matching k is present in the file or not. There are a number of complex searching algorithms to serve the purpose of searching. The linear search and binary search methods are relatively straight forward methods of searching. 2.2.1 Sequential search In this method, we start to search from the beginning of the list and examine each element till the end of the list. If the desired element is found we stop the search and return the index of that element. If the item is not found and the list is exhausted the search returns a zero value. In the worst case the item is not found or the search item is the last (n^th) element. For both situations we must examine all n elements of the array so the order of magnitude or complexity of the sequential search is n. i.e., O(n). The execution time for this algorithm is proportional to n that is the algorithm executes in linear time. The algorithm for sequential search is as follows, Algorithm : sequential search Input : A, vector of n elements K, search element Output : j –index of k Method : i=1 While(i<=n) { if(A=k) { write("search successful") write(k is at location i) exit(); } else i++ if end while end write (search unsuccessful); algorithm ends. 2.2.2 Binary search Binary search method is also relatively simple method. For this method it is necessary to have the vector in an alphabetical or numerically increasing order. A search for a particular item with X resembles the search for a word in the dictionary. The approximate mid entry is located and its key value is examined. If the mid value is greater than X, then the list is chopped off at the (mid-1)^th location. Now the list gets reduced to half the original list. The middle entry of the left-reduced list is examined in a similar manner. This procedure is repeated until the item is found or the list has no more elements. On the other hand, if the mid value is lesser than X, then the list is chopped off at (mid+1)^th location. The middle entry of the right-reduced list is examined and the procedure is continued until desired key is found or the search interval is exhausted. The algorithm for binary search is as follows, Algorithm : binary search Input : A, vector of n elements K, search element Output : low –index of k Method : low=1,high=n While(low<=high-1) { mid=(low+high)/2 if(k<a[mid]) high=mid else low=mid if end } while end if(k=A[low]) { write("search successful") write(k is at location low) exit(); } else write (search unsuccessful); if end; algorithm ends. click here for more details: http://www.vyomworld.com/gate/cs/ada/2.2.asp Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers