03/11/17

Searching for Elements

• Given an array of marks and names, is there
someone who got X marks?
• If X occurs in the Marks array, return the index
CS1100 of the position where it occurs.
Introduction to Programming • If the numbers are randomly arranged, there is no
option but to scan the entire array to be sure.
Searching and Structures
• Would the task be simpler if the marks were
Madhu Mutyam arranged in sorted order?
Department of Computer Science and Engineering
Indian Institute of Technology Madras – Like finding a word in a dictionary

Course Material – SD, SB, PSK, NSN, DK, TAG – CS&E, IIT M 1 2
SD, PSK, NSN, DK, TAG – CS&E, IIT M

Searching in a Sorted Array Divide and Conquer

• Given an array of marks and names sorted in Largest Smallest

descending order of marks, is there someone who

got X marks?
• If X is high (say 92/100), one could start • Look at the middle element
scanning from the left. • If array[middle] = = X, done
• If X is low (say 47/100), one could scan the array • If array[middle] > X, look only in the right part
right to left.
• Else look for the number only in the left part
• But what if we do not know whether X is high or
low? • The problem is reduced into a smaller problem
– new problem is half the size of the original one
• Recursively apply this strategy
SD, PSK, NSN, DK, TAG – CS&E, IIT M 3 SD, PSK, NSN, DK, TAG – CS&E, IIT M 4

Divide and Conquer Binary Search (also called Binary Chop)

• Two indexes define the range of searching • Starts with the full sorted array
– left = 0 and right = N-1
• The range of search are the elements between left
and right including array[left] and array[right]
left middle = (left + right)/2 right • Search terminates if right < left
• Otherwise
• If array[middle] > X look only in the right part – If (array[middle] == X) return middle
– If (array[middle] < X) left = middle +1
– Else right = middle -1

newLeft newMiddle right

= middle+1
SD, PSK, NSN, DK, TAG – CS&E, IIT M 5 SD, PSK, NSN, DK, TAG – CS&E, IIT M 6

1
 03/11/17

Binary Search (bsearch in stdlib.h – elements increasing Complexity of Binary Search

order)
int BinarySearch(int value, int array[ ], int n){
int left = 0, right = n-1;
while (left <= right){
middle = (left+right)/2;
if (array[middle] == value) return middle;
if (array[middle] < value) left = middle +1;
else right = middle -1;
}
return INFINITY; /*calling function must interpret this
correctly! */
} After each inspection the array reduces by half. For an array of size
N there are about log2N inspections in the worst case.
SD, PSK, NSN, DK, TAG – CS&E, IIT M 7 SD, PSK, NSN, DK, TAG – CS&E, IIT M 8

Complexity: Recurrence Equation Finding Student with X marks

• Let n be the size of the array char *findStudent (int x, char names[][COL], int marks[],
• Let the function T(n) represent the time complexity of int n)
solving the problem of size n {
• In each call the problem is reduced by half int index = BinarySearch(x, marks[], n);
– one comparison in each call if (index == n) return “no such student”;
• T(n) = 1 + T(n/2) else return names[index];
• Solving this gives us the complexity log2(n) } return NULL;
n 128 256 512 1024 2048 4096 … T(n) = 1 + T(n/2)
T(n/2) = 1 + T(n/4)
log n 7 8 9 10 11 12 …
T(n/4) = 1 + T(n/8) Above function assumes that names are corresponding to
. marks, and marks are in decreasing order.
.
T(2) = 1 + T(1)
SD, PSK, NSN, DK, TAG – CS&E, IIT M 9 SD, PSK, NSN, DK, TAG – CS&E, IIT M 10
log(n) equations =1+1

Marks and Names Structures

• We kept Marks in an integer array and Names in • Collection of one or more variables, possibly of
a corresponding two dimensional array different types, grouped together under a single
– could keep Names in an array of pointers name for easy handling.
– memory reserved as per requirements • For example - a structure which represents a
• The connection between the two arrays was via point in a two dimensional plane
the shared index struct point{ A mechanism for defining
• Can we keep them in the same array? int x; compound data types

– one option – keep first three characters for marks and int y;
convert them while processing By itself it reserves
};
– a better option – use structures no storage
SD, PSK, NSN, DK, TAG – CS&E, IIT M 11 SD, PSK, NSN, DK, TAG – CS&E, IIT M 12

2
 03/11/17

Point in 2D à 2 Integers Marks and Names

• Different ways of declaring structure variables struct student{
struct point{ char *name; name could itself be a struct made up
of first name, middle name and last
int x; int mark; name…
Nested structures are allowed
int y; }s1, s2;
} point1, point2;
struct student s1, s2;
struct point point1, point2; struct student s1 = { “Ramesh” , 79 };
struct point point1 = { 3 , 2 };

SD, PSK, NSN, DK, TAG – CS&E, IIT M 13 SD, PSK, NSN, DK, TAG – CS&E, IIT M 14

A Rectangle Defining New Types

struct rectangle{ • ‘typedef’ keyword is used for creating new data
struct point pt1; • types
struct point pt2; • For example:
}rect1; • typedef int Age;
• Accessing points in the rectangle Age myAge = 99;
rect1.pt1.x = 4; • typedef and Structures:
rect1.pt1.y = 5; typedef struct point pointType;
Or pointType point1, point2;
rect1.pt1 = { 4, 5 }; • This is equivalent to: struct point point1, point2;
SD, PSK, NSN, DK, TAG – CS&E, IIT M 15 SD, PSK, NSN, DK, TAG – CS&E, IIT M 16

Operations on Structures Functions and Structures

• Structures may be copied by assignment statement • Structure as function argument
• The address of the structure (use &) can be passed
to functions and can be returned by functions int isOrigin(pointType pt){
– one can pass an entire structure if (pt.x == 0 && pt.y == 0)
– one can pass some components of a structure return 1;
– one can pass a pointer to a structure
else
• Structures may not be compared
return 0;
}

SD, PSK, NSN, DK, TAG – CS&E, IIT M 17 SD, PSK, NSN, DK, TAG – CS&E, IIT M 18

3
 03/11/17

Structures and Functions A Screen and its Centre Point

• Structure as return type struct rectangle screen;
struct point middle;
pointType makePoint(int x, int y){ struct point makePoint(int, int);
pointType temp;
temp.x = x; screen.pt1 = makePoint(0, 0);
temp.y = y; Observe there is no confusion
screen.pt2 = makePoint(XMAX, YMAX);
return temp; between the two occurrences of
x and y
middle =
} makePoint((screen.pt1.x+screen.pt2.x)/2,
(screen.pt1.y+screen.pt2.y)/2);
SD, PSK, NSN, DK, TAG – CS&E, IIT M 19 SD, PSK, NSN, DK, TAG – CS&E, IIT M 20

Adding Two Points

/* addPoints: add two points */
struct point addPoints(struct point p1, struct point p2)
{ p1.x += p2.x;
p1.y += p2.y;
return p1;}

•
Note that the local changes to p1 •
would not affect the point p1;
pass by value
•
SD, PSK, NSN, DK, TAG – CS&E, IIT M 21