05 Arrays - Searching

The document discusses arrays and provides details about: 1) Arrays are a data structure that store a collection of data elements of the same type in contiguous memory locations. Arrays allow for fast access of elements using indexes. 2) The key properties of arrays are that they store homogeneous elements, the elements are stored in contiguous memory locations, and elements can be accessed randomly using an index in O(1) time. 3) Common array operations like indexing, insertion, deletion, and searching have different time complexities depending on whether elements are accessed at the beginning, middle, or end of the array.

Uploaded by

Ashraf Uzzaman Saleh

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

68 views32 pages

05 Arrays - Searching

Uploaded by

Ashraf Uzzaman Saleh

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 32

Data Structures- Arrays

 Data structure
 A particular way of storing and organising data in a
computer so that it can be used efficiently
 Types of data structures
 Based on memory allocation
o Static (or fixed sized) data structures (Arrays)
o Dynamic data structures (Linked lists)
 Based on representation
o Linear (Arrays/linked lists)
o Non-linear (Trees/graphs)
Array: motivation
 You want to store 5 numbers in a computer
 Define 5 variables, e.g. num1, num2, ..., num5
 What, if you want to store 1000 numbers?
 Defining 1000 variables is a pity!
 Requires much programming effort
 Any better solution?
 Yes, some structured data type
o Array is one of the most common structured data types
o Saves a lot of programming effort (cf. 1000 variable names)
What is an Array?
 A collection of data elements in which
 all elements are of the same data type, hence
homogeneous data
o An array of students’ marks
o An array of students’ names
o An array of objects (OOP perspective!)
 elements (or their references) are stored at
contiguous/ consecutive memory locations
 Array is a static data structure
 An array cannot grow or shrink during program
execution – its size is fixed
Basic concepts
 Array name (data)
 Index/subscript (0...9)
 The slots are numbered sequentially
starting at zero (Java, C++)
 If there are N slots in an array, the
index will be 0 through N-1
 Array length = N = 10
 Array size = N x Size of an element = 40
 Direct access to an element
Homogeneity
 All elements in the array must have the same
data type
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 30 45 50 60 65 70 80

Index: 0 1 2 3 4
Value: 5.5 10.2 18.5 45.6 60.5

Index: 0 1 2 3 4
Value: ‘A’ 10.2 55 ‘X’ 60.5 Not an array
Contiguous Memory
 Array elements are stored at contiguous memory
locations
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 30 45 50 60 65 70 80

 No empty segment in between values (3 & 5 are

empty – not allowed)
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 45 60 65 70 80
Using Arrays
 Array_name[index]
 For example, in Java
 System.out.println(data[4]) will display 0

 data[3] = 99 will replace -3 with 99

Some more concepts
data[ -1 ] always illegal
data[ 10 ] illegal (10 > upper bound)
data[ 1.5 ] always illegal
data[ 0 ] always OK
data[ 9 ] OK

Q. What will be the output of?

1. data[5] + 10
2. data[3] = data[3] + 10
Array’s Dimensionality
 One dimensional (just a linear list)
 e.g., 5 10 18 30 45 50 60 65 70 80
 Only one subscript is required to access an individual
element
 Two dimensional (matrix/table)
 e.g., 2 x 4 matrix (2 rows, 4 columns)

Col 0 Col 1 Col 2 Col 3

Row 0 20 25 60 40
Row 1 30 15 70 90
Two dimensional Arrays
 Let, the name of the two dimensional array is M
20 25 60 40
30 15 70 90

 Two indices/subscripts are required (row, column)

 First element is at row 0, column 0
 M0,0 or M(0, 0) or M[0][0] (more common)
 What is: M[1][2]? M[3][4]?
Array Operations
 Indexing: inspect or update an element using its index.
Performance is very fast O(1)
randomNumber = numbers[5];
numbers[20000] = 100;
 Insertion: add an element at certain index
– Start: very slow O(n) because of shift
– End : very fast O(1) because no need to shift
 Removal: remove an element at certain index
– Start: very slow O(n) because of shift
– End : very fast O(1) because no need to shift
 Search: performance depends on algorithm
1) Linear: slow O(n) 2) binary : O(log n)
 Sort: performance depends on algorithm
1) Bubble: slow O(n2) 2) Selection: slow O(n2)
3) Insertion: slow O(n2) 4)Merge : O (n log n)
One Dimensional Arrays in Java
 To declare an array follow the type with (empty) []s
int[] grade; //or
int grade[]; //both declare an int array

 In Java arrays are objects so must be created with the new

keyword
 To create an array of ten integers:
int[] grade = new int[10];
Note that the array size has to be specified, although it can be
specified with a variable at run-time
Arrays in Java
 When the array is created memory is reserved for its contents

 Initialization lists can be used to specify the initial values of an

array, in which case the new operator is not used
int[] grade = {87, 93, 35}; //array of 3 ints

 To find the length of an array use its .length property

int numGrades = grade.length; //note: not .length()!!
Searching Algorithms
 Search for a target (key) in the search space
 Search space examples are:
 All students in the class
 All numbers in a given list
 One of the two possible outcomes
 Target is found (success)
 Target is not found (failure)
Searching Algorithms
Index: 0 1 2 3 4
Value: 20 40 10 30 60

Target = 30 (success or failure?)

Target = 45 (success or failure?)
Search strategy?
List Size = N = 5
Min index = 0
Max index = 4 (N - 1)
Sequential Search

 Search in a sequential order

 Termination condition
 Target is found (success)
 List of elements is exhausted (failure)
Sequential Search

Index: 0 1 2 3 4
Value: 20 40 10 30 60

Target = 30
Step 1: Compare 30 with value at index 0
Step 2: Compare 30 with value at index 1
Step 3: Compare 30 with value at index 2
Step 4: Compare 30 with value at index 3 (success)
Sequential Search

Index: 0 1 2 3 4
Value: 20 40 10 30 60

Target = 45
Step 1: Compare 45 with value at index 0
Step 2: Compare 45 with value at index 1
Step 3: Compare 45 with value at index 2
Step 4: Compare 45 with value at index 3
Step 5: Compare 45 with value at index 4
Failure
Sequential Search Algorithm

Given: A list of N elements, and the target

1. index  0
2. Repeat steps 3 to 5
3. Compare target with list[index]
4. if target = list[index] then
return index // success
else if index >= N - 1
return -1 // failure
5. index  index + 1
Binary Search

 Search through a sorted list of items

 Sorted list is a pre-condition for Binary Search!
 Repeatedly divides the search space (list) into
two
 Divide-and-conquer approach
Binary Search: An Example (Key  List)