Class Notes (835,722)
Canada (509,348)
CPSC 319 (12)
Lecture 3

CPSC 319 Lecture 3: 03 Searching

3 Pages
80 Views
Unlock Document

Department
Computer Science
Course
CPSC 319
Professor
Leonard Manzara
Semester
Winter

Description
Searching and Sorting Terminology - Data: independent facts, observations, or events - Record: the data pertaining to a unique object o Sometimes called an element o Consists of one or more fields - Field: a constituent part of a record, usually consisting of a single data element o Has a specified type and size - File: a collection of records - Key: the data field used to select or order records o May or may not be unique for a set of records - Primary Key: the field used first for selecting or sorting records o E.g. Last names in a telephone book - Secondary Key: the field used if 2 or more records have equal primary keys o E.g. First names in a telephone book - Satellite Data: data in the non-key fields, not used when sorting or selecting records o E.g. Phone numbers in a telephone book - Search: an operation that returns a pointer to a record that matches a key value or nil - Sorting: arranges the items of a list into ascending (or descending) order comparing keys Sequential Search - Basic idea: starting at the beginning of a list, compare each successive item to a query key until we find a match or reach end of the list - Works on both sorted and unsorted lists - Can be used on arrays and linked lists - Likely to be the fastest algorithm on small lists (up to about 20 records) - Java code to search an integer array: int sequentialSearch(int[] array, int key) { for (int i = 0; i < array.length; i++) if (array[i] == key) return i; // success return -1; // failure: key not found } - In the best case we find a match immediately (perform 1 comparison) - In the worst case (an unsuccessful search/match found at the end), n comparisons occur - On average, (# + 1) / 2 comparisons are performed - Is an O(n) algorithm Binary Search - Works only on a sorted array of records - Basic idea: Divide the array in half by locating the middle term o If the query key matches this item, return o If the key is less than the middle item, divide the left sub-array in half o If the key is greater than the middle item, divide the rig
More Less

Related notes for CPSC 319

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit