Searching Techniques

Searching Techniques
This chapter explores various searching techniques. The process of identifying or

finding a particular record is called Searching. You often spend time in searching
for any desired item. If the data is kept properly in sorted order, then searching
becomes very easy and efficient. In this chapter, you will get to know the basic
concepts of searching that are used in the data structure and case of
programming also
What is searching?
Searching is an operation or a technique that helps finds the place of a given
element or value in the list. Any search is said to be successful or unsuccessful
depending upon whether the element that is being searched is found or not.
Some of the standard searching technique that is being followed in the data
structure is listed below:
Linear Search or Sequential Search

Binary Search
What is Linear Search?

This is the simplest method for searching. In this technique of searching, the
element to be found in searching the elements to be found is searched
sequentially in the list. This method can be performed on a sorted or an unsorted
list (usually arrays). In case of a sorted list searching starts from 0th element and
continues until the element is found from the list or the element whose value is
greater than (assuming the list is sorted in ascending order), the value being
searched is reached.
As against this, searching in case of unsorted list also begins from the 0th element
and continues until the element or the end of the list is reached.
Example
The list given below is the list of elements in an unsorted array. The array contains ten
elements. Suppose the element to be searched is '46', so 46 is compared with all the
elements starting from the 0th element, and the searching process ends where 46 is
found, or the list ends.
The performance of the linear search can be measured by counting the comparisons
done to find out an element. The number of comparison is 0(n).
Algorithm for linear search

It is a simple algorithm that searches for a specific item inside a list. It operates
looping on each element O(n) unless and until a match occurs or the end of the
array is reached.
algorithm Seqnl_Search(list, item)

Pre: list != ;
Post: return the index of the item if found, otherwise: 1
index <- fi
while index < list.Cnt and list[index] != item //cnt: counter variable
index <- index + 1
end while
if index < list.Cnt and list[index] = item
return index
end if
return: 1
end Seqnl_Search
What is Binary Search?

Binary search is a very fast and efficient searching technique. It requires the list to
be in sorted order. In this method, to search an element you can compare it with
the present element at the center of the list. If it matches, then the search is
successful otherwise the list is divided into two halves: one from the 0th element
to the middle element which is the center element (first half) another from the
center element to the last element (which is the 2nd half) where all values are
greater than the center element.
The searching mechanism proceeds from either of the two halves depending
upon whether the target element is greater or smaller than the central element. If
the element is smaller than the central element, then searching is done in the first
half, otherwise searching is done in the second half.
Algorithm for Binary Search
 algorithm Binary_Search(list, item)

 Set L to 0 and R to n: 1
 if L > R, then Binary_Search terminates as unsuccessful
 else
 Set m (the position in the mid element) to the floor of (L + R) / 2
 if Am < T, set L to m + 1 and go to step 3
 if Am > T, set R to m: 1 and go to step 3
 Now, Am = T,
 the search is done; return (m)
Sorting Techniques
In this chapter you will be dealing with the various sorting techniques and their
algorithms used to manipulate data structure and its storage. Sorting method can
be implemented in different ways - by selection, insertion method, or by merging.
Various types and forms of sorting methods have been explored in this tutorial.
What is sorting?
Sorting refers to the operation or technique of arranging and rearranging sets of
data in some specific order. A collection of records called a list where every
record has one or more fields. The fields which contain a unique value for each
record is termed as the key field. For example, a phone number directory can be
thought of as a list where each record has three fields - 'name' of the person,
'address' of that person, and their 'phone numbers'. Being unique phone number
can work as a key to locate any record in the list.
Sorting is the operation performed to arrange the records of a table or list in

some order according to some specific ordering criterion. Sorting is performed
according to some key value of each record.
The records are either sorted either numerically or alphanumerically. The records
are then arranged in ascending or descending order depending on the numerical
value of the key. Here is an example, where the sorting of a lists of marks
obtained by a student in any particular subject of a class.
Categories of Sorting
The techniques of sorting can be divided into two categories. These are:
Internal Sorting
External Sorting
Internal Sorting: If all the data that is to be sorted can be adjusted at a time
in the main memory, the internal sorting method is being performed.
External Sorting: When the data that is to be sorted cannot be
accommodated in the memory at the same time and some has to be kept in
auxiliary memory such as hard disk, floppy disk, magnetic tapes etc, then
external sorting methods are performed.
Efficiency of sorting techniques

To get the amount of time required to sort an array of 'n' elements by a
particular method, the normal approach is to analyze the method to find the
number of comparisons (or exchanges) required by it. Most of the sorting
techniques are data sensitive, and so the metrics for them depends on the
order in which they appear in an input array.
Various sorting techniques are analyzed in various cases and named these
cases as follows:
Best case
Worst case
Average case
Hence, the result of these cases is often a formula giving the average time
required for a particular sort of size 'n.' Most of the sort methods have time
requirements that range from O(nlog n) to O(n2).
Types of sorting techniques

Bubble Sort
Selection Sort
Merge Sort
Insertion Sort
Quick Sort
Heap Sort

Searching Techniques

Uploaded by

Copyright:

Available Formats

Searching Techniques

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Searching Techniques

Uploaded by

Copyright:

Available Formats

Searching Techniques

This chapter explores various searching techniques. The process of identifying or

Linear Search or Sequential Search

What is Linear Search?

Algorithm for linear search

algorithm Seqnl_Search(list, item)

What is Binary Search?

Algorithm for Binary Search

 algorithm Binary_Search(list, item)

Sorting is the operation performed to arrange the records of a table or list in

Efficiency of sorting techniques

Types of sorting techniques

You might also like