Questions and Answers
What is a prerequisite for binary search to work?
What does the linear search algorithm return if the target value is not found?
At which index does the binary search algorithm start comparing the target value?
What is the main difference between linear search and binary search?
Signup and view all the answers
What happens in the linear search algorithm when the target value is found?
Signup and view all the answers
How does the binary search algorithm narrow down the search range in each iteration?
Signup and view all the answers
What is the optimal size of m in Jump Search Algorithm?
Signup and view all the answers
What is the purpose of the linear search in the Jump Search Algorithm?
Signup and view all the answers
What is the condition to jump to the next block in the Jump Search Algorithm?
Signup and view all the answers
What is the value of m in Step 1 of the Jump Search Algorithm?
Signup and view all the answers
In which step of the Jump Search Algorithm is the linear search performed?
Signup and view all the answers
What is the purpose of Step 3 in the Jump Search Algorithm?
Signup and view all the answers
What is the primary purpose of the binary search algorithm?
Signup and view all the answers
What is the termination condition of the binary search algorithm?
Signup and view all the answers
What happens when the target element is greater than the middle element in the binary search algorithm?
Signup and view all the answers
What is the time complexity of the binary search algorithm?
Signup and view all the answers
What is the purpose of the mid
variable in the binary search algorithm?
Signup and view all the answers
What happens when the target element is found in the binary search algorithm?
Signup and view all the answers
What is the purpose of the start
and finish
variables in the binary search algorithm?
Signup and view all the answers
What is the return value of the binarySearch
function when the target element is not found?
Signup and view all the answers
What is the purpose of the while
loop in the binary search algorithm?
Signup and view all the answers
What is the prerequisite for using the binary search algorithm?
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 < 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 <= finish) {
int mid = (start + finish) / 2;
if (target == Arr[mid])
return mid;
else if (target < 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.