COMP1210: Linear Search Algorithm

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is a prerequisite for binary search to work?

The array must be unsorted

The array must be empty

The array must be sorted (correct)

The target value must be in the array

What does the linear search algorithm return if the target value is not found?

-1 (correct)

The last index of the array

The first index of the array

At which index does the binary search algorithm start comparing the target value?

The first index of the array

A random index of the array

The middle index of the array (correct)

The last index of the array

What is the main difference between linear search and binary search?

Linear search works on unsorted arrays, binary search works on sorted arrays Signup and view all the answers

What happens in the linear search algorithm when the target value is found?

The algorithm returns the index of the target value Signup and view all the answers

How does the binary search algorithm narrow down the search range in each iteration?

By eliminating half of the array based on the comparison Signup and view all the answers

What is the optimal size of m in Jump Search Algorithm?

√n Signup and view all the answers

What is the purpose of the linear search in the Jump Search Algorithm?

To search for the item in the current block Signup and view all the answers

What is the condition to jump to the next block in the Jump Search Algorithm?

If item != A[i] and item > A[i] Signup and view all the answers

What is the value of m in Step 1 of the Jump Search Algorithm?

√n Signup and view all the answers

In which step of the Jump Search Algorithm is the linear search performed?

Step 4 Signup and view all the answers

What is the purpose of Step 3 in the Jump Search Algorithm?

To repeat the comparison process Signup and view all the answers

What is the primary purpose of the binary search algorithm?

To find an element in a sorted array Signup and view all the answers

What is the termination condition of the binary search algorithm?

When the start index is greater than the finish index Signup and view all the answers

What happens when the target element is greater than the middle element in the binary search algorithm?

The start index is set to the middle index + 1 Signup and view all the answers

What is the time complexity of the binary search algorithm?

O(log n) Signup and view all the answers

What is the purpose of the `mid` variable in the binary search algorithm?

To store the middle index of the current search range Signup and view all the answers

What happens when the target element is found in the binary search algorithm?

The algorithm returns the index of the target element Signup and view all the answers

What is the purpose of the `start` and `finish` variables in the binary search algorithm?

To store the start and finish indices of the current search range Signup and view all the answers

What is the return value of the `binarySearch` function when the target element is not found?

-1 Signup and view all the answers

What is the purpose of the `while` loop in the binary search algorithm?

To search for the target element in the current search range Signup and view all the answers

What is the prerequisite for using the binary search algorithm?

The array must be sorted in ascending order Signup and view all the answers

Study Notes

Searching Algorithms

Linear Search

A very basic and simple search algorithm
Searches an element or value in a given array by traversing the array from the start until the desired element or value is found
Does not require the array to be sorted
Steps of implementation:
- Traverse the array using a for loop
- In every iteration, compare the target value with the current value of the array
- If the values match, return the current index of the array
- If the values do not match, move on to the next array element
- If no match is found, return -1
Sample code:

int linearSearch(int values[], int target, int n)
{
      for (int i = 0; i &lt; n; i++)
      {
            if (values[i] == target)
            {
                  return i;
            }
      }
      return -1;
}

Binary Search

Works only on sorted arrays
Begins by comparing an element in the middle of the array with the target value
If the target value matches the element, its position in the array is returned
If the target value is less than the element, the search continues in the lower half of the array
If the target value is greater than the element, the search continues in the upper half of the array
By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration
Sample code:

int binarySearch(int Arr[], int target, int start, int finish) {
       while (start &lt;= finish) {
             int mid = (start + finish) / 2;
             if (target == Arr[mid])
                   return mid;
             else if (target &lt; Arr[mid])
                   finish = mid - 1;
             else
                   start = mid + 1;
       }
       return -1;
}

Jump Search

A combination of linear and binary search
It has been shown that the optimal size of the block is √n
Steps for Jump Search Algorithms:
- Set i=0 and m = √n
- Compare A[i] with item
- If A[i] != item and A[i] < item, then jump to the next block
- Repeat step 2 while m < n-1
- If A[i] > item, then move to the beginning of the current block and perform a linear search
- Exit

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Learn about linear search, a basic search algorithm used to find an element in an array. Understand the steps involved in its implementation.