Data Structure (KCS-
301)
SEARCHING
4 Lecture
Chapter
2
Contents
Sr Major and Detailed Coverage Area Hr
# s
8 Searching 4
Linear Search, Binary Search, Hashing
2
Searchin
g
3
Computer systems are often used to store large amounts of data
from which individual records must be retrieved according to some
search criterion. Thus the efficient storage of data to facilitate fast
searching is an important issue.
Following are the typical searching methodology used:
Linear Search
Binary Search
Hashing
3
Linear
Search
4
Linear search is a very simple search algorithm. In this type of search, a
sequential search is made over all items one by one. Every items is checked
and if a match founds then that particular item is returned otherwise search
continues till the end of the data collection. The run time complexity is O(n)
How linear search works?
It sequentially checks each element of the list for the target value until a
match is found or until all the elements have been searched.
Algorithm
LinearSearch (Array A, Step 6: Set i to i + 1 [continuation of
algorithm]
Value x) Step 1: Start Step 7: Go to Step 4
Step 2: Set i to 1 Step 8: Print Element x found at
Step 3: Set n to length of position i and go to step 10
A Step 4: if i > n then go Step 9: Print element not
to step 9 found Step 10: Stop
Step 5: if A[i] = x then go 4
Linear Search C
code
5
#include <stdio.h>
//continuation of
program for (c = 0; c
int main()
< n; c++)
{
{
int array[100], search, c, n;
if (array[c] ==
search)
printf("Enter the number of elements in
array\n");
{
printf("%d is present at
scanf("%d",&n); location %d.\n", search,
c+1);
printf("Enter %d integer(s)\ break;
}
n", n); for (c = 0; c < n; c++) }
scanf("%d", &array[c]);
return
if (c == n)
}0;
printf("%d is not present in
printf("Enter the number to array.\n", search);
search\n"); scanf("%d", &search);
5
Linear Search Recursive C
code
6
#include <stdio.h>
//continuation of program
int x = 3; // x is the element to be
/* Recursive function to search x in
arr[l..r] */ searched for int index = recSearch(arr,
int recSearch(int arr[], int l, int r, int x) 0, n-1, x);
{ if (index != -1)
printf("Element %d is present at index
if (r < l)
%d", x, index);
return - else
1; printf("Element %d is not present",
if (arr[l] x);
== x) return 0;
return l; }
return
recSearc
h(arr,
l+1, r, x);
}
int main() 6
Linear Search
cont…
7
Time Complexity
Case Best Case Worst Case Average Case
Item is present 1 n n/2
Item not present n n n
Class Work
Your CR (Class Representative) went for a walk in a garden. There are many
trees in the garden and each tree has an English alphabet on it. While CR
was walking, he/she noticed that all trees with vowels on it are not in good
state. She/he decided to take care of them. So, he/she asked you to tell him
the count of such trees in the garden.
Note
Input::The following letters are vowels:Input
'A', 'E',
: 'I', 'O', 'U' ,'a','e','i','o' and 'u'.
“nBBZLaosnm” “JHkIsnZtTL”
Output : 2 number of vowels in 1 st input
Explanation: Output is 2: and
1 in second
input is 1
7
Divide &
Conquer
8
In divide and conquer approach, the problem in hand, is divided into smaller
sub- problems and then each problem is solved independently. When we keep
on dividing the sub-problems into even smaller sub-problems, we may
eventually reach at a stage where no more dividation is possible. Those
"atomic" smallest possible sub-problem (fractions) are solved. The solution of
all sub-problems is finally merged in order to obtain the solution of original
problem.
8
Divide & Conquer
cont…
9
Broadly, we can understand divide-and-conquer approach as three step
process.
Divide/Break: This step involves breaking the problem into smaller sub-
problems. Sub-problems should represent as a part of original problem.
This step generally takes recursive approach to divide the problem until
no sub-problem is further dividable. At this stage, sub-problems become
atomic in nature but still represents some part of actual problem.
Conquer/Solve: This step receives lot of smaller sub-problem to be solved.
Generally
at this level, problems are considered 'solved' on their own.
Merge/Combine: When the smaller sub-problems are solved, this stage
recursively combines them until they formulate solution of the original
problem.
The following computer algorithms are based on
divide-and-conquer programming approach
Binary Search
9
Binary
Search
10
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 sorted form. It search a particular item
by comparing the middle most item of the collection. If match occurs then index of
item is returned. If middle item is greater than item then item is searched in sub-array
to the right of the middle item other wise item is search in sub-array to the left of the
middle item. This process continues on sub-array as well until the size of sub-array
reduces to zero.
How binary search works?
Before the sort computation starts, bottom is initialized to 0 and top is initialized to n-1
i.e. 9.
First, we shall determine the half of the array by using this formula : mid = (top +
bottom)/ 2. Here it is, (9 + 0 ) / 2 = 4 (integer value of 4.5). So 4 is the mid of array.
10
Binary Search
cont…
11
Now we compare the value stored at location 4, with the value being searched i.e. 31.
We find that value at location 4 is 27, which is not a match. Because value is greater
than 27 and we have a sorted array so we also know that target value must be in
upper portion of the array. So make bottom = mid + 1
i.e. 4 + 1 = 5
So at this point, bottom is 5 and top is 9. Second, we need to find the new mid value
again i.e. mid =
(bottom + top ) /2 = (5 + 9) / 2 = 14 / 2 = 7. So 7 is the mid of the array
Now we compare the value stored at location 7, with the value being searched i.e. 31.
We find that value at location 7 is 35, which is not a match. Because value is less than
35 and we have a sorted array so we also know that target value must be in lower
portion of the array. So make top = mid - 1 i.e. 7 - 1 = 6
11
Binary Search
cont…
12
So at this point, bottom is 5 and top is 6. Third, we need to find the new mid value again
i.e. mid = (bottom + top ) /2 = (5 + 6) / 2 = 1 1 / 2 = 5. The value stored at location 5 is
a match and conclude that the target value 31 is stored at location 5.
Binary search pseudo code
INPUT: A[], n, ITEM [continuation of Pseudo
bottom
code] IF (ITEM = A[mid]
0 top n
–1 THEN
REPEAT OUTPUT: ITEM
mid (bottom + FOUND ELSE
top ) / 2 IF (ITEM < OUTPUT: ITEM
A[mid]) THEN NOT FOUND
top mid – 1
ELSE IF (ITEM >
A[mid]) THEN
bottom mid +
12
1 END IF
Binary Search C
code
13
#include
//continuation of
<stdio.h> program do
{
int main()
{ mid = (bottom +
int n, a[30], item, i, j, mid, top, top) / 2; if (item <
bottom; printf("Enter # of a[mid])
elements :\n"); top = mid - 1;
scanf("%d", &n); else if (item >
printf("Enter elements in a[mid]) bottom =
ascending order\n"); mid + 1;
for (i = 0; i < n; i++) } while (item != a[mid] && bottom
{ <= top); if (item == a[mid])
scanf("%d", &a[i]); printf("Binary search
} successful!!\n"); else
printf("\nEnter the item to printf("\n Search failed);
search\n"); return 0;
scanf("%d", &item); } 13
Binary Search Recursive C
code
14
// A recursive binary search function. It returns
location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{ //continuation of
if (r >= l) program int
{ main(void)
int mid = l + (r - l)/2; {
// If the element is present at the int arr[] = {2, 3, 4,
10, 40};
middle itself if (arr[mid] == x) return
mid; int n = sizeof(arr)/
sizeof(arr[0]);
// If element is smaller than mid, then it int x = 10;
can only be present
int result = binarySearch(arr, 0,
// in left subarray
n-1, x); if (result == -1)
if (arr[mid] > x) return
binarySearch(arr, l, mid-1, x); printf("Element is not present in
array") else
// Else the element can only be present
printf("Element is present at index
in right subarray
%d", result);
return binarySearch(arr, mid+1, r, x);
return 0;
}
} 14
// We reach here when element is not present
Binary Search
cont…
15
Time Complexity
Case Best Case Worst Case Average Case
Item is present 1 log2(n) log2(n/2)
Item not present log2(n) log2(n) log2(n)
Class Work
Its been a few days since Ankit is acting weird and finally you(best friend)
came to know that its because his proposal has been rejected.
He is trying hard to solve this problem but because of the rejection thing he
can't really focus. Can you help him? The question is: Given a number n , find
if n can be represented as the sum of 2 desperate numbers (not necessarily
different) , where desperate numbers are those which can be written in the
form of (a*(a+1))/2 where a > 0 .
Input : The first input line contains an integer n (1 ≤ n ≤ 10^9).
Output : Print "YES", if n can be represented as a sum of two desperate
numbers, otherwise print "NO".
DATA STRUCTURE KCS 301
THANKS
16