SEARCHING
AND HASHING
Searching is a process of
checking and finding
an element from a list of elements. Let A be a collection of data elements,
i.e., A is a linear array of say n elements. If we want to find the presence of
an element “data” in A, then we have to search for it. The search is successful
if data does appear in A and unsuccessful if otherwise. There are several types
of searching techniques; one has some advantage(s) over other.
Following are the three
important searching techniques :
1. Linear or
Sequential Searching
2. Binary
Searching
3. Fibonacci Search
1. LINEAR OR SEQUENTIAL SEARCHING:
In linear search, each element of an array is
read one by one sequentially and it is compared with the desired element. A
search will be unsuccessful if all the elements are read and the desired
element is not found.
ALGORITHM FOR LINEAR SEARCH:
Let A be an array of n
elements, A[1],A[2],A[3], ...... A[n]. “data” is the element to be searched.
Then this algorithm will find the location “loc” of data in A.
Set loc = – 1, if the search is unsuccessful.
1. Input an array A of n
elements and “data” to be searched and initialise loc = – 1. 2. Initialise i =
0; and repeat through step
3 if (i < n) by
incrementing i by one .
3. If (data = A[i]) (a) loc
= i (b) GOTO step 4
4. If (loc > 0) (a)
Display “data is found and searching is successful”
5. Else (a) Display “data
is not found and searching is unsuccessful”
6. Exit
//PROGRAM TO IMPLEMENT SEQUENTIAL SEARCHING
//CODED
AND COMPILED USING TURBO C
#include
void
main()
{
char
opt;
int
arr[20],n,i,item;
clrscr();
printf
(“\nHow many elements you want to enter in the array : ”);
scanf
(“%d”,&n);
for(i=0;
i < n;i++)
{
printf (“\nEnter element %d : ”,i+1);
scanf
(“%d”, &arr[i]);
}
printf (“\n\nPress any key to continue....”);
getch();
do
{
clrscr();
printf
(“\nEnter the element to be searched : ”);
scanf
(“%d”,&item);
//Input
the item to be searched
for(i=0;i
< n;i++)
{ if item == arr[i])
{ printf (“\n%d found at position
%d\n”,item,i+1);
break;
}
}
/*End
of for*/
if (i
== n)
printf
(“\nItem %d not found in array\n”,item);
printf
(“\n\nPress (Y/y) to continue : ”);
fflush(stdin);
scanf
(“%c”,&opt);
}
while(opt
== ‘Y’ || opt == ‘y’);
}
=====
TIME COMPLEXITY:
Time Complexity of the
linear search is found by number of comparisons made in searching a record. In
the best case, the desired element is present in the first position of the
array, i.e., only one comparison is made. So f (n) = O(1). In the Average case,
the desired element is found in the half position of the array, then f (n) =
O[(n + 1)/2]. But in the worst case the desired element is present in the nth
(or last) position of the array, so n comparisons are made. So f (n) = O(n +
1).
BINARY SEARCH:
Binary search is an
extremely efficient algorithm when it is compared to linear search. Binary
search technique searches “data” in minimum possible comparisons. Sup-pose the
given array is a sorted one, otherwise first we have to sort the array
elements. Then apply the following conditions to search a “data”.
1. Find the middle element
of the array (i.e., n/2 is the middle element if the array or the sub-array
contains n elements).
2. Compare the middle
element with the data to be searched, then there are follow-ing three cases.
(a) If it is a desired
element, then search is successful.
(b) If it is less than
desired data, then search only the first half of the array, i.e., the elements
which come to the left side of the middle element.
(c) If it is greater than
the desired data, then search only the second half of the array, i.e., the
elements which come to the right side of the middle element. Repeat the same
steps until an element is found or exhaust the search area.
Suppose we have an array of
7 elements Following steps are generated if we binary search a data = 45 from
the above array.
Step 1: LB=0;UB=6 mid = (0
+ 6)/2 = 3 A[mid] = A[3] = 30
Step 2: Since (A[3] <
data) - i.e., 30 < 45 - reinitialize the variable LB, UB and mid LB=3UB=6
mid = (3 + 6)/2 = 4 A[mid] = A[4] = 40
Step 3: Since (A[4] <
data) - i.e., 40 < 45 - reinitialize the variable LB, UB and mid LB=4 , UB=6,
mid = (4 + 6)/2 = 5 A[mid] = A[5] = 45
Step 4: Since (A[5] ==
data) - i.e., 45 == 45 - searching is successful.
PROGRAM
//PROGRAM TO IMPLEMENT THE BINARY SEARCH
//CODED AND COMPILED USING TURBO C
#include
void
main()
{
char
opt;
int
arr[20], start,end,middle,n,i,item;
clrscr();
printf (“\nHow many elements you want to enter
in the array : ”);
scanf
(“%d”,&n);
for(i=0;
i < n; i++)
{
printf (“\nEnter element %d : ”,i+1);
scanf
(“%d”,&arr[i]);
}
printf
(“\n\nPress any key to continue...”);
getch();
do
{
clrscr();
printf
(“\nEnter the element to be searched : ”);
scanf
(“%d”,&item);
start=0;
end=n –
1;
middle=(start
+ end)/2;
while(item
!= arr[middle] && start <= end)
{
if
(item > arr[middle]) start=middle+1; else end=middle-1;
middle=(start+end)/2;
}
if
(item==arr[middle])
printf(“\n%d
found at position %d\n”,item,middle + 1);
if
(start>end)
printf
(“\n%d not found in array\n”,item);
printf
(“\n\nPree (Y/y) to continue : ”);
fflush(stdin);
scanf
(“%c”,&opt);
}
while(opt
== ‘Y’ || opt == ‘y’);
}
/*End of main()*/
===========
TIME COMPLEXITY:
Time Complexity is measured
by the number f (n) of comparisons to locate “data” in A, which contain n
elements. Observe that in each comparison the size of the search area is
reduced by half. Hence in the worst case, at most log2 n comparisons required. So
f (n) = O([log2 n ]+1).
Time Complexity in the
average case is almost approximately equal to the running time of the worst
case.
Binary Search
Binary search is a fast search algorithm with run-time
complexity of Ο(log n). This search algorithm works on the principle of divide
and conquer. For this algorithm to work properly, the data collection should be
in the sorted form.
Binary search looks for a particular item by comparing the
middle most item of the collection. If a match occurs, then the index of the item
is returned. If the middle item is greater than the item, then the item is
searched in the sub-array to the left of the middle item. Otherwise, the item
is searched for in the sub-array to the right of the middle item. This process
continues on the sub-array until the size of the subarray reduces to
zero.
How Binary Search Works?
For a binary search to work, it is mandatory for the target
array to be sorted. We shall learn the process of binary search with a
pictorial example. The following is our sorted array and let us assume that we
need to search the location of value 31 using binary search.
First, we shall determine half of the array by using this formula −
mid = low + (high - low) / 2
Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So,
4 is the mid of the array.
Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.
We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location
7 with our target value 31.
The value stored at location 7 is not a match, rather it is more than what we are looking for. So, the value must be in the lower part from this location.
Hence, we calculate the mid again. This time it is 5.
We compare the value stored at location 5 with our target
value. We find that it is a match.
Binary search halves the searchable items and thus reduces
the count of comparisons to be made to very less numbers.
ALGORITHM FOR
BINARY SEARCH:
Let A be an array of n
elements A[1], A[2], A[3], ...... A[n]. “Data” is an element to be searched.
“mid” denotes the middle location of a segment (or array or sub-array) of the
element of A. LB and UB is the lower and upper bound of the array which is
under consideration.
1. Input an array A of n
elements and “data” to be sorted
2. LB = 0, UB = n; mid =
int ((LB+UB)/2)
3. Repeat step 4 and 5
while (LB <= UB) and (A[mid] ! = data)
4. If (data < A[mid])
5. (a) UB = mid–1 ( b) LB =
mid + 1
6. Mid = int ((LB + UB)/2)
7. If (A[mid]== data) (a)
Display “the data found”
8. Else (a) Display “the
data is not found”
9. Exit
PSEUDOCODE
The pseudocode of binary search algorithms should look like
this −
PROCEDURE BINARY_SEARCH
A ← sorted array
n ← size of array
x ← value to be
searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound <
lowerBound
EXIT: x does not
exists.
set midPoint =
lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] <
x
set lowerBound =
midPoint + 1
if A[midPoint] >
x
set upperBound =
midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
=================
No comments:
Post a Comment