professor-curious-logo
professor-curious-logo
  1. AP Computer Science A
FlashcardFlashcard
Study GuideStudy GuideQuestion BankQuestion BankGlossaryGlossary

What are the differences between Linear Search and Binary Search?

Linear Search: Works on unsorted data, O(n) time complexity. | Binary Search: Requires sorted data, O(log n) time complexity.

Flip to see [answer/question]
Flip to see [answer/question]
Revise later
SpaceTo flip
If confident

All Flashcards

What are the differences between Linear Search and Binary Search?

Linear Search: Works on unsorted data, O(n) time complexity. | Binary Search: Requires sorted data, O(log n) time complexity.

What does the following code output?

java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(2, 4, 6, 8, 10));
int target = 6;
System.out.println(linearSearch(arr, target));

2

What does the following code output?

java
int[] arr = {1, 3, 5, 7, 9};
int target = 2;
System.out.println(linearSearch(arr, target));

-1

Identify the error in the following code:

java
public static int linearSearch(ArrayList<String> array, int n) {
    for (int i = 0; i < array.size(); i++) {
        if (array.get(i) == n) {
            return i;
        }
    }
    return -1;
}

The method expects an ArrayList of Strings but compares the elements to an integer n. The parameter type should be String n.

Complete the following code snippet for linear search in an integer array:

java
public static int linearSearch(int[] array, int n) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == n) {
            // Complete this line
        }
    }
    return -1;
}

return i;

What does the following code output?

java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 10, 15, 20));
int target = 5;
System.out.println(linearSearch(arr, target));

0

What does the following code output?

java
int[] arr = {5, 10, 15, 20};
int target = 25;
System.out.println(linearSearch(arr, target));

-1

How is Linear Search applied in real-world scenarios?

Searching for a specific product in a small online store inventory, finding a specific contact in a small phone book, or searching for a file in a directory.