What We Will Cover
Continuations
Homework Questions?
^ top
10.1: Array Basics
Objectives
At the end of the lesson the student will be able to:
- Declare and allocate memory for arrays
- Initialize array values
- Select elements of an array
|
^ top
10.1.1: Introduction to Arrays
Array: a single name for a collection of identically-typed data values
- Arrays are a type of data structure
-- a way to organize data
- An array is used to process a collection of data of the same type
- Why do we need arrays?
- Imagine keeping track of 5 test scores, or 100, or 1000 in memory
- How would you name all the variables?
- How would you process each of the variables?
- Arrays provide a convenient solution to these problems
- You keep all the data for an entire array using a single identifier
- Each element is identified uniquely by an index number
For Example
- One-dimensional array is like single row of data in spreadsheet or table
score[0] |
score[1] |
score[2] |
score[3] |
score[4] |
| 90 |
95 |
87 |
89 |
98 |
- Top row shows the indices for an array named "
score"
- Individual items are referenced by the index (a.k.a. subscript)
- All the values are of the same type:
int
- Array length is 5
^ top
10.1.2: Declaring and Allocating Arrays
- Consider an array named
score containing 5 values
- You declare and allocate memory for this array like this:
int[] score; // declaration
score = new int[5]; // allocation
Which is equivalent to:
int[] score = new int[5]; // Java style
Which is equivalent to:
int score[] = new int[5]; // C++ style
This is like declaring 5 variables of type int numbered as follows:
score[0], score[1], score[2], score[3], score[4]
The value in brackets is called an index or subscript
Individual values in an array are called items or elements
The number of indexed variables in an array is the size of the array
- The largest index is one less than the size
- The first index value is zero
Array declaration syntax:
DataType[] arrayName = new DataType[length];
Arrays can be of any data type
All the variables of an array are always of the same data type
- Known as the base type of the array
Allocated dynamically with operator new
Once created, you cannot change the number of elements
Reference Types
- Arrays assignments are different than for primitive types
- Arrays names are reference types because arrays are objects in Java
- For instance:
double[] prices;
prices = new double[6];
First line declares a reference variable of type array-of-doubles
Second line creates an array object in memory and assigns the location to the prices reference variable
^ top
10.1.3: Selecting an Array Element
- Array elements are selected by using the array name and an index
int myScore = score[0];
An index can be any integer expression
int n = 2;
score[n + 1] = 99;
You can use an indexed array variable like any regular variable
score[0] = score[1] + 1;
score[0]++;
^ top
10.1.4: Initializing Array Values
- You can assign a value to an array element any time after it is declared
int[] score = new int[5];
score[0] = 90;
score[1] = 95;
score[2] = 87;
score[3] = 89;
score[4] = 98;
Static Initialization
- You can also initialize array elements in the declaration statement
- Called static initialization
- Use a comma-separated list inside curly-braces
int[] score = {90, 95, 87, 89, 98};
Produces the same array
The length of the array is determine automatically from the list
Default Values
- If you do not assign a value, then the array elements are assigned default values:
- Integer (
byte, short, int, long): 0
- Floating-point (
float, double): 0.0
- Character (
char): '\u0000'
- Boolean:
false
- Objects:
null
^ top
10.1.5: Array Index Out of Range
- A common error is using a nonexistent index
- Index values for int
score[5] are the values 0 through 4
- An index value not allowed by the array declaration is out of range
- Using an out of range index value produces an error message!
ArrayIndexOutOfBoundsException
For example, using the following code:
1
2
3
4
5
6
7
8
9
10
11
|
public class ScoreArray {
public static void main(String[] args) {
int[] score = {90, 95, 87, 89, 98};
System.out.println(score[0]);
System.out.println(score[1]);
System.out.println(score[2]);
System.out.println(score[3]);
System.out.println(score[4]);
//System.out.println(score[5]); // out of bounds
}
}
|
- Trying to use an index less than 0 or more than the length - 1 causes an error
ArrayIndexOutOfBoundsException
^ top
10.1.6: Summary
- Arrays are convenient ways to process a list of data
- You can declare an array in different ways:
int[] score; // declaration
score = new int[5]; // allocation
Which is equivalent to:
int[] score = new int[5]; // Java style
Which is equivalent to:
int score[] = new int[5]; // C++ style
Each array element is referenced by name and an index inside of square brackets
You can use an indexed array variable like any regular variable
score[0] = score[1] + 1;
You can initialize array elements individually with an assignment statement
score[0] = 90;
A more convenient way is to use an initializer list
int score[] = {90, 95, 87, 89, 98};
The programmer must be very careful to keep the array index within bounds
Otherwise an error message will result
ArrayIndexOutOfBoundsException
^ top
Exercise 10.1
In this exercise we explore declaring, allocating and assigning values to arrays containing lists of data.
Specifications
- Save the following code file as
MyArrays.java.
- Declare and allocate an array for a list of 100 integer grades.
- Declare and allocate an array of char vowels, assigning a value to each array element.
- Declare and allocate an array of double-precision values holding the temperatures
25, 30 and 40 in order.
- Declare and allocate a list of strings holding the names:
Able, Baker and Charlie.
- Make sure your code compiles after every array that you declare and allocate.
- Submit your source-code file as the answer to this exercise.
1
2
3
4
5
6
7
8
9
10
11
12
|
public class MyArrays {
public static void main(String[] args) {
// A list of 100 integer grades
// A list of chars holding vowels
// A list of doubles holding temperatures
// A list of Strings holding names
}
}
|
^ top
10.2: Arrays and Loops
Objectives
At the end of the lesson the student will be able to:
- Use loops to process array elements
- Calculate statistics on lists of data stored in arrays
|
^ top
10.2.1: Processing Array Values in a Loop
- Array processing is easily done in a loop
- A
for loop is commonly used to process array elements
- For example, we can use a loop to display the contents of an array
int[] scores = {90, 95, 87, 89, 98};
for (int i = 0; i < scores.length; i++) {
System.out.println(scores[i]);
}
Note the use of the constant length in the array loop
Initializing an Array
- Similarly, we can initialize array elements to a known value:
int[] scores = new int[5];
for (int i = 0; i < score.length; i++) {
System.out.println(score[i]);
}
^ top
10.2.2: Using the Enhanced for Loop with Arrays
- In addition to the standard for loop, Java provides an enhanced for loop
- This loop is specially designed to work with arrays and other collections of data
- In other languages, this loop is known as the foreach loop
- Syntax:
for (type variableName : arrayName) {
// statements to execute
}
Note that you do not code initialization, test and increment statements
Instead, you declare a variable that refers to each array element
Within the loop, you use this variable to access each array element
To understand how this works, lets look at an example
Example of Enhanced for Loop
int[] score = {90, 95, 87, 89, 98};
for (double aScore : score) {
System.out.println(aScore);
}
Example Comparison to Regular for Loop
int[] scores = {90, 95, 87, 89, 98};
for (int i = 0; i < scores.length; i++) {
System.out.println(scores[i]);
}
^ top
10.2.3: Calculating Statistics on an Array of Values
- Since we can use a loop to access every item in an array, we can sum the array values
- For example:
1
2
3
4
5
6
7
8
9
10
11
|
public class ArraySum {
public static void main(String [] args) {
int[] data = {5, 4, 3, 2, 1};
int sum = 0;
for (int i = 0; i < data.length; i++) {
sum = sum + data[i];
System.out.print(data[i] + ", ");
}
System.out.println("\nsum = " + sum);
}
}
|
- What code would we add to show the average of the array values?
- What would we change to find the maximum array value?
- How would we find the minimum array value?
- What is the easiest way to initialize minimum and maximum values?
^ top
10.2.4: Copying an Array
- Sometimes you need to copy the values in one array to another array
- This is easy to accomplish with a loop
Example of Copying an Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class ArrayCopier {
public static void main(String[] args) {
double[] prices1 = {0.99, 1.99, 2.99, 3.99, 4.99};
double[] prices2 = new double[5];
// Copy an array
for (int i = 0; i < prices1.length; i++) {
prices2[i] = prices1[i];
}
// Display the copy
for (int i = 0; i < prices1.length; i++) {
System.out.println(i + ": " + prices1[i]
+ " = " + prices2[i]);
}
}
}
|
^ top
10.2.5: Summary
- You can use loops to access every array element
- For example, to display all the elements of an array:
int[] score = {90, 95, 87, 89, 98};
for (int i = 0; i < score.length; i++) {
System.out.println(score[i]);
}
In addition to the standard for loop, Java provides an enhanced for loop
This loop is specially designed to work with arrays and other collections of data
For example, to display all the elements of an array:
int[] score = {90, 95, 87, 89, 98};
for (double aScore : score) {
System.out.println(aScore);
}
Another use for loops is to sum the values of an array
1
2
3
4
5
6
7
8
9
10
11
|
public class ArraySum {
public static void main(String [] args) {
int[] data = {5, 4, 3, 2, 1};
int sum = 0;
for (int i = 0; i < data.length; i++) {
sum = sum + data[i];
System.out.print(data[i] + ", ");
}
System.out.println("\nsum = " + sum);
}
}
|
- You can also use loops to compute an average, find a minimum or a maximum
- Loops also allow you to copy all the values from one array and save them in another array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class ArrayCopier {
public static void main(String[] args) {
double[] prices1 = {0.99, 1.99, 2.99, 3.99, 4.99};
double[] prices2 = new double[5];
// Copy an array
for (int i = 0; i < prices1.length; i++) {
prices2[i] = prices1[i];
}
// Display the copy
for (int i = 0; i < prices1.length; i++) {
System.out.println(i + ": " + prices1[i]
+ " = " + prices2[i]);
}
}
}
|
^ top
Exercise 10.2
In this exercise we explore using a loop to access every array element.
Specifications
- Save the following code file as
ArrayMinimum.java.
- Change the name of the class to
ArrayMinimum
- Add code to find the minimum value of the array of data.
- Submit your source-code file as the answer to this exercise.
1
2
3
4
5
6
7
8
9
10
11
|
public class ArraySum {
public static void main(String [] args) {
int[] data = {5, 4, 3, 2, 1};
int sum = 0;
for (int i = 0; i < data.length; i++) {
sum = sum + data[i];
System.out.print(data[i] + ", ");
}
System.out.println("\nsum = " + sum);
}
}
|
^ top
10.3: Arrays and Methods
Objectives
At the end of the lesson the student will be able to:
- Pass arrays elements as arguments
- Pass entire arrays as arguments
- Use arrays in methods
- Return arrays from methods
- Obtain values from the array passed to the
main method
|
^ top
10.3.1: Array Elements as Arguments
- Indexed variables can be arguments to methods
- For example, if a program contains these declarations:
public static void main(String[] args) {
int i = 0;
int[] myArray = new int[10];
}
static void myMethod(int n) { /* some code */ }
You can use indexed variables myArray[0] through myArray[9] as method arguments
For instance:
myMethod(myArray[0]);
myMethod(myArray[3]);
myMethod(myArray[i]);
Example Using Indexed Variables in a Method Call
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import java.text.NumberFormat;
public class ArrayPrices {
public static void main(String[] args) {
double[] prices = {12.3, 23.45, 32.456};
for (int i = 0; i < prices.length; i++) {
showPrice(prices[i]);
}
}
static void showPrice(double value) {
NumberFormat currency =
NumberFormat.getCurrencyInstance();
String formattedItem = currency.format(value);
System.out.println(formattedItem);
}
}
|
^ top
10.3.2: Arrays as Method Parameters
- You can use an entire array as an argument to a method
- When passing the array, you code just the array name without
[ ] brackets
showArray(days);
The called method has access to all the array elements
You do not know the length of the array that will be passed
- The size of the array can be different every time you call the method
To access every array element in order, you can use the enhanced for loop
If you need to know the size of the array, you can use the length variable of the array
Note that you could easily overload the showArray() method for different array types
Example Method That Uses an Enhanced for Loop to Display an Array
static void showArray(String[] values) {
for (String item : values) {
System.out.println(item);
}
}
Example Method That Uses a for Loop to Display an Array
static void showArray(String[] values) {
for (int i = 0; i < values.length; i++) {
System.out.println(values[i]);
}
}
^ top
10.3.3: Changing Array Elements in Methods
- All types in Java are passed-by-value (a.k.a. call-by-value)
- When method is called, the value of each argument is copied to its corresponding parameter
- A method only gets a copy of the variable's value
- Thus, variables used as arguments cannot be changed within the method
- However, arrays are objects and an array variable contains a reference value
- A reference value is the location of the array in memory
- Thus, the reference to the array is copied to the method parameter
- This means that any action taken on the parameter is actually taken on the original array
- The effect of this is that array elements can be changed in methods
- You can see this effect in the following example
For Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import java.util.Scanner;
public class ArrayFiller {
public static final int NUMBER_ITEMS = 3;
public static void main(String[] args) {
int[] data = new int[NUMBER_ITEMS];
fillUp(data);
showArray(data);
}
// Fills an array with values from the keyboard
static void fillUp(int[] data) {
Scanner input = new Scanner(System.in);
for (int i = 0; i < data.length; i++) {
System.out.print("Enter number: ");
data[i] = input.nextInt();
}
}
// Displays an array to the screen
static void showArray(int[] values) {
for (int i = 0; i < values.length; i++) {
System.out.println(i + ": " + values[i]);
}
}
}
|
^ top
10.3.4: Returning an Array
- Methods can return an array reference
- You can specify an array type as a return value for a method
- For example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class ArrayMaker {
public static void main(String arg[]) {
char[] vowels;
vowels = makeVowels();
for(char ch : vowels) {
System.out.println(ch);
}
}
public static char[] makeVowels() {
char[] vowels = new char[5];
vowels[0] = 'a';
vowels[1] = 'e';
vowels[2] = 'i';
vowels[3] = 'o';
vowels[4] = 'u';
return vowels;
}
}
|
^ top
10.3.5: Method main Parameters
- Recall that every Java program must have a
main() method with this signature:
public static void main(String[] args)
The JVM begins executing code at the main() method of the specified class
Notice that the parameter args is an array of Strings
Arguments are passed to the array by the operating system
All words after the class name passed in the args array
java ArgEcho Java Rules!
Number of parameters can be determined from args.length
System.out.println(args.length);
Name args is a convention -- can be named anything
Example Program Using Arguments Passed from the Operating System
1
2
3
4
5
6
7
8
|
class ArgEcho {
public static void main(String[] args) {
for (int i = 0; i < args.length; i++) {
System.out.print("Arg " + i + ": ");
System.out.println(args[i]);
}
}
}
|
>java ArgEcho Hi Mom!
Arg 0: Hi
Arg 1: Mom!
^ top
10.3.6: Summary
- You can pass an array to a method
- The method can change elements of the array
- Because arrays are reference types
- Location of the array passed to the method
- When an element is accessed, the original location is used
- A method can create and return an array
- The operating system can send arguments to the
String[] parameter of method main()
- You can access these elements in your program like any other array
Check Yourself
- What is the syntax for specifying an entire array as a parameter for a method?
- When you pass an array as a parameter, do you include the square brackets?
- Why can a method change the elements of an array?
- What is the syntax for returning an array from a method?
- How do you send arguments from an operating system to a Java program
^ top
Exercise 10.3
- Label this exercise: Exercise 10.3
- Submit all exercises for this lesson in one file unless instructed otherwise
- Complete the following and record the answers to any questions in exercise10.txt.
Specifications
- The following declarations were used to create an array:
final int NUMGRADES = 500;
double[] grades = new double[NUMGRADES];
Write a method header for a method named sortArray that accepts grades as a parameter. Record your solution in exercise10.txt.
- Write a method named
oneMore which has a parameter for an array of int's and adds one to each element of the array. Use the following starter code to get started and submit your solution along with these exercises.
public class AddOneApp {
public static void main(String[] args) {
int[] a = {0, 2, 4, 6, 8};
showArray(a);
//oneMore(a);
showArray(a);
}
// Displays an array to the screen
static void showArray(int[] values) {
for (int i = 0; i < values.length; i++) {
System.out.println(values[i]);
}
}
}
^ top
10.4: Programming With Arrays
Objectives
At the end of the lesson the student will be able to:
- Test array equality
- Compute statistics on arrays of data
- Search an array
- Sort an array
- Choose the best algorithm for searching an array
|
^ top
10.4.1: Testing Array Equality
- Remember that arrays are objects
- Thus, array variables are reference types
- Tests using
== checks if the memory addresses are the same
if (a == b)
For example, what does the following code print?
1
2
3
4
5
6
7
8
9
10
11
|
public class ArrayChecker {
public static void main(String[] args) {
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
if (a == b) {
System.out.println("a == b");
} else {
System.out.println("a != b");
}
}
}
|
- Both arrays have the same elements
- However, they are stored at different locations in memory
- Thus, they do not have the same memory address
Testing Array Elements for Equality
- To test array elements for equality, you need to check each array element
- We can define an equals method that returns true if and only if all the array elements are equal
- Arrays must also be the same length
- Updating our original code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public class ArrayTester {
public static void main(String[] args) {
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
if (a == b) {
System.out.println("a == b");
} else {
System.out.println("a != b");
}
if (equals(a, b) == true) {
System.out.println("a equals b: ");
} else {
System.out.println("a not equal to b");
}
}
public static boolean equals(int[] a, int[] b) {
boolean match = true; //tentatively
if (a.length != b.length) {
match = false;
} else {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) match = false;
}
}
return match;
}
}
|
^ top
10.4.2: Using Arrays Interactively
- An entered value can be used to allocate space for an array
- The size of an array is known as its dimension
- Sizing an array at run time is referred to as run-time dimensioning
User Input of Array Values
- Consider the case of reading user input into an array
- As the array is being filled, some elements are unused
- Note that there is no automatic mechanism to detect how many items have been entered
- The programmer must keep track of the progress
- In these situations, you use an
int variable to keep track of the index
- You can see this technique in the following example
Example of Runtime Dimensioning
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
import java.util.Scanner;
class ArrayInput {
private static Scanner input = new Scanner(System.in);
public static void main(String [] args) {
System.out.print("How many items: ");
int numItems = input.nextInt();
int[] data = new int[numItems];
fillUp(data);
showArray(data);
}
// Fills an array with values from the keyboard
static void fillUp(int data[]) {
for (int i = 0; i < data.length; i++) {
System.out.print("Enter number "
+ (i + 1) + ": ");
data[i] = input.nextInt();
}
}
// Displays an array to the screen
static void showArray(int[] values) {
for (int item : values) {
System.out.println(item);
}
}
}
|
Check Yourself
- When is the size of the array decided?
- What does the
data array contain before the user enters any values?
- What is the value of
data.length after one item has been entered?
- How do we know how many items have been entered by the user?
^ top
10.4.3: Using Part of an Array
- In some situations, you need some but not all of the indexed values of an array
- For instance, a user is entering data and you want to calculate a minimum value of the data entered so far
- In this situation, you keep track of the starting and end points of the data using the array indexes
- As an example, what if we wnated to find the minimum value of part of an array
- We would need to know the starting index and the ending index
- Then we could use a loop to find a minimum value between the start and end indexes
- This is shown in the following method:
Example Method to Find a Minium Value Over Part of an Array
static int findMin(int[] data, int start, int end) {
int indexOfMin = start;
for (int i = start + 1; i <= end; i++) {
if (data[i] < data[indexOfMin]) {
indexOfMin = i;
}
}
return indexOfMin;
}
^ top
10.4.4: Sequential Search of an Array
- Sometimes you want to find out if a particular value exists in an array
- This is known as searching an array
- An easy and straightforward algorithm is sequential search
- In sequential search you:
- Start at the beginning of the array
- Compare each value in the array until:
- If the value is found, then return found
- If you reach the end of the array, return not found
- The following example demonstrates sequential search
Example of Sequential Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
import java.util.Scanner;
public class ArraySearch {
public static void main(String [] args) {
Scanner input = new Scanner(System.in);
int[] data = {-12, -4, 7, 10, 14, 21, 29};
System.out.print("Enter value to find: ");
int valueToFind = input.nextInt();
boolean found = false;
int count = 0;
while ((!found) && (count < data.length)) {
if (valueToFind == data[count]) {
found = true;
}
count++;
}
if (found) {
System.out.print("Found ");
} else {
System.out.print("Did not find ");
}
System.out.println(valueToFind + " in "
+ count + " comparisons");
}
}
|
- On average, would it be any faster to start searching at the end of an array?
- If an array is sorted, then we can program faster methods -- binary search
^ top
10.4.5: Sorting an Array
- Sorting is a common task for computers, for example:
- Sort numbers in ascending order
- Sort numbers in descending order
- Sort strings in alphabetic order
- Many different algorithms for sorting, including:
- Bubble sort - move item up until in right place
- Insertion sort - add elements to list one at a time
- Selection sort - pick 1st, then 2nd, etc.
- Quick sort - divide and conquer
Selection Sort
- Selection sort is one of the easiest -- but not the most efficient
- General algorithm:
- Find the smallest element
- Swap with the first element
- Find the smallest element in the rest of the list
- Swap with the first element of the rest of the list
- Repeat until the list is sorted
| Pass |
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
a[6] |
| Original |
10 |
7 |
29 |
14 |
-4 |
-12 |
21 |
| First |
-12 |
7 |
29 |
14 |
-4 |
10 |
21 |
| Second |
-12 |
-4 |
29 |
14 |
7 |
10 |
21 |
| Third |
-12 |
-4 |
7 |
14 |
29 |
10 |
21 |
| Fourth |
-12 |
-4 |
7 |
10 |
29 |
14 |
21 |
| Fifth |
-12 |
-4 |
7 |
10 |
14 |
29 |
21 |
| Sixth |
-12 |
-4 |
7 |
10 |
14 |
21 |
29 |
- How many passes were needed for a seven element array?
Selection Sort Code
- Following is selection sort code
- Have added some statements to show action for each pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public class SelectionSort {
public static void main(String [] args) {
int[] a = {10, 7, 29, 14, -4, -12, 21};
System.out.print("Original array: ");
showArray(a);
sort(a);
System.out.print("\nSorted array: ");
showArray(a);
}
public static void showArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ", ");
}
System.out.println();
}
static void sort(int[] a) {
int index, indexOfMin;
for (index = 0; index < a.length - 1; index++) {
indexOfMin = findMin(a, index, a.length - 1);
swap(a, index, indexOfMin);
System.out.print("Pass#" + index + ": ");
showArray(a);
}
}
static int findMin(int[] a, int start, int end) {
int indexOfMin = start;
for (int i = start + 1; i <= end; i++) {
if (a[i] < a[indexOfMin]) {
indexOfMin = i;
}
}
return indexOfMin;
}
static void swap(int[] a, int first, int second) {
System.out.println("\nSwapping " + a[first]
+ " with " + a[second]);
int temp = a[first];
a[first] = a[second];
a[second] = temp;
}
}
|
- Note that every element in the array must have a value
- Can the array have duplicate items?
- Also note that the larger task was broken into smaller tasks using methods
- Helps to organize the program and improve clarity
What About Bubble Sort?
- Bubble sort is another algorithm that is easy to understand and use
- General algorithm:
- Make
array.length passes through the array
- For each pass, compare each array element with the next element
- If the current element is larger than the next one, swap them
- Not an efficient sorting algorithm
- Sometimes simple algorithms perform poorly
- Simple algorithms are still useful because: easy to program and understand
- If better performance is needed, you can replace with a better algorithm
- More information: Sorting Algorithms
- Includes Java source code
^ top
10.4.6: Binary Search
- Once an array is sorted, can use binary search to find an item
- Binary search is much faster than sequential search
Binary Search Algorithm
- A key value is searched for among the values stored in the array.
- Two index variables
lowIdx and highIdx are used to limit the scope of the search.
- The search proceeds until the element searched for is found or the scope between
lowIdx and highIdx is exhausted.
- The index
middleIdx is computed as
(lowIdx + highIdx) / 2.
- If
key = data[middleIdx] the search is successful.
- If
key < data[middleIdx], highIdx is lowered to middleIdx.
If key > data[middleIdx], lowIdx is raised to middleIdx. - If the scope between
lowIdx and highIdx is exhausted, the search is unsuccessful.
- Demonstration applet: BinarySearch
Binary Search Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
public class BinarySearch {
public static void main(String [] args) {
int[] a = {-12, -4, 7, 10, 14, 21, 29};
int key = 14;
System.out.print("Searching array: ");
showArray(a);
int index = binarySearch(a, key);
System.out.println("Index of " + key
+ " = " + index);
}
static void showArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ", ");
}
System.out.println();
}
// find the index of key in array a
// return -1 if key is not found
static int binarySearch(int[] a, int key) {
int step = 0;
int lowIdx = 0;
int highIdx = a.length - 1;
int middleIdx;
while (lowIdx <= highIdx) {
step++;
middleIdx = (lowIdx + highIdx) / 2;
System.out.println("Step#" + step
+ " lowIdx=" + lowIdx
+ " highIdx=" + highIdx
+ " middleIdx=" + middleIdx);
if (a[middleIdx] == key) {
return middleIdx; // just right
} else if (a[middleIdx] < key) {
lowIdx = middleIdx + 1; // too small
} else {
highIdx = middleIdx - 1; // too big
}
}
return -1; // not found
}
}
|
How Much Faster is Binary Search?
- Given the sorted array:
| a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
a[6] |
| -12 |
-4 |
7 |
10 |
14 |
21 |
29 |
- How many steps to find the value of 14 using sequential search?
- How many steps to find the value of 14 using binary search?
- On average for an array of n elements:
- Sequential search takes n / 2 steps
- Binary search takes 2 * log2(n) + 2 steps maximum
- Translating to some array sizes:
| Array Size |
floor(log2(n)) + 1 |
| 1 |
1 |
| 10 |
4 |
| 100 |
7 |
| 1000 |
10 |
| 10,000 |
14 |
- Binary search quickly becomes worth the effort of its implementation
- Binary search is one algorithm a programming professional should know!
^ top
10.4.7: Summary
- Arrays are objects and threfore == may not work as you expect
- Tests using == checks if the memory addresses are the same
- When you test for array equality, you usually want to know if the values in the array are the same
- You can write your own method for this like:
public static boolean equals(int[] a, int[] b) {
boolean match = true; //tentatively
if (a.length != b.length) {
match = false;
} else {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) match = false;
}
}
return match;
}
You can easily enter values into an array for later processing
A "partially filled array" is one in which values are stored in an initial segment of the array
Can search arrays sequentially to find a value
Sorting algorithms can sort an array into ascending or descending order
If an array is sorted, can use binary search to speed the search process
Check Yourself
- If you compare two arrays with the same values, why does
== return false?
- When is the size of the array decided?
- If you want to use only part of an array, what must you keep track of?
- Why is binary search faster than sequential search?
- What condition must an array be in before you can use binary search?
^ top
Exercise 10.4
In this exercise we look at selection sort.
Specifications
- Label this exercise: Exercise 10.4
- Record the contents of the following array after each pass of SelectionSort.
int[] array = {9, 21, -7, 2, 87, -19, 47}
^ top
Wrap Up
^ top
Home
| WebCT
| Announcements
| Schedule
| Expectations
| Course info
Help
| FAQ's
| HowTo's
| Links
Last Updated: November 03 2005 @17:10:18
|
