Welcome to Revolution 3.0
Experience a brand new Edukatte!
Computer Science Module 1 Question 2(Searching)
Unit2
Jul 13, 2024
Estimated reading time:
Contains all relevant information regarding searching of lists, linear and binary.
Linear Search
Traverses a list entirely, comparing the search value to each element in the list until either the search value is found, returning its index or it traverses the entire list, displaying that the element was not found.
Code
int linear_search(int arr\[], int n, int x)
{
for (int i = 0; i < n; i++) {
if (arr\[i] == x) {
return i; // Element found, return its index
}
}
return -1; // Element not found
}
Binary Search
- List must be sorted (1 mark in any past paper)
- Searches for an element by halving the list at each pass
- The mid point of the list is found by taking the sum of the first and last index of the list and dividing it by 2
- The search value is compared to this mid element
- If the element is greater than the search value low = mid and low = low + 1
- If the element is less than the search value high = mid and high = high - 1
- This is repeated until either the element is found and its index is returned or low > high ( the search value does not exist)
Code
int binary_search(int arr\[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr\[i] == x) {
return i; // Element found, return its index
}
}
return -1; // Element not found
}