7.5 Searching
1 min read•december 30, 2022
Athena_Codes
Milo Chang
Athena_Codes
Milo Chang
Linear / Sequential Search
One of the main applications of ArrayLists is to search, that is to see if an element is actually in an and to return its index if it is.
The simplest searching algorithm, and the only one we will learn in this unit, is . This algorithm goes through the list element by element (thus the names sequential and linear) until the element is found. If the element is not found, -1 is returned.
ArrayList Implementation
Here is its implementation for an :
public static int linearSearch(<Integer> array, int n) { for (int i = 0; i < array.size(); i++) { if (array.get(i) == n) { return i; } } return -1; }
Integer Array Implementation
Here is the implementation for a regular integer array:
public static int linearSearch(int[] array, int n) { for (int i = 0; i < array.length; i++) { if (array[i] == n) { return i; } } return -1; }
There are other searching algorithms, but the only other important one to know is covered in Unit 10.
Key Terms to Review (3)
ArrayList
: ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.Binary Search
: Binary search is an efficient algorithm used to locate a target value within a sorted array by repeatedly dividing the search interval in half.Linear/Sequential Search
: Linear search is a simple searching algorithm that checks each element in a list one by one until it finds a match or reaches the end of the list. It is commonly used when there is no specific order or structure to the data.7.5 Searching
1 min read•december 30, 2022
Athena_Codes
Milo Chang
Athena_Codes
Milo Chang
Linear / Sequential Search
One of the main applications of ArrayLists is to search, that is to see if an element is actually in an and to return its index if it is.
The simplest searching algorithm, and the only one we will learn in this unit, is . This algorithm goes through the list element by element (thus the names sequential and linear) until the element is found. If the element is not found, -1 is returned.
ArrayList Implementation
Here is its implementation for an :
public static int linearSearch(<Integer> array, int n) { for (int i = 0; i < array.size(); i++) { if (array.get(i) == n) { return i; } } return -1; }
Integer Array Implementation
Here is the implementation for a regular integer array:
public static int linearSearch(int[] array, int n) { for (int i = 0; i < array.length; i++) { if (array[i] == n) { return i; } } return -1; }
There are other searching algorithms, but the only other important one to know is covered in Unit 10.
Key Terms to Review (3)
ArrayList
: ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.Binary Search
: Binary search is an efficient algorithm used to locate a target value within a sorted array by repeatedly dividing the search interval in half.Linear/Sequential Search
: Linear search is a simple searching algorithm that checks each element in a list one by one until it finds a match or reaches the end of the list. It is commonly used when there is no specific order or structure to the data.
Resources
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.