Disclaimer
The solution of question or notes are written by either student or taken from some publications , so it is the responsibility of viewer to check whether answers are correct or incorrect.
Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.
Based on the type of search operation, these algorithms are generally classified into two categories:
1. Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search.
2. Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example: Binary Search.
Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set.
How Linear Search Works?
ยท Step 1: First, read the search element (Target element) in the array.
ยท Step 2: Set an integer i = 0 and repeat steps 3 to 4 till i reaches the end of the array.
ยท Step 3: Match the key with arr[i].
ยท Step 4: If the key matches, return the index. Otherwise, increment i by 1.
Illustration of Linear Search:
Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 20
Step 1: Set i = 0 and check key with arr[0].
Step 2: key and arr[0] are not the same. So make i = 1 and match key with arr[1].
Step 3: arr[1] and key are different. Increment i and compare key with arr[2].
Step 4: arr[2] is not the same with key. Increment i and compare key with arr[3].
Step 5: key and arr[3] are different. Make i = 4 and compare key with arr[4].
Step 6: key and arr[4] are not same. Make i = 5 and match key with arr[5].
We can see here that key is present at index 5.
// C code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
#include <stdio.h>
int search(int arr[], int N, int x)
{
int i;
for (i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
int result = search(arr, N, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Linear Search Approach: A simple approach is to do a linear search. The time complexity of the Linear search is O(n). Another approach to perform the same task is using Binary Search.
Binary Search Approach:
Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).
Binary Search Algorithm: The basic steps to perform Binary Search are:
ยท Sort the array in ascending order.
ยท Set the low index to the first element of the array and the high index to the last element.
ยท Set the middle index to the average of the low and high indices.
ยท If the element at the middle index is the target element, return the middle index.
ยท If the target element is less than the element at the middle index, set the high index to the middle index โ 1.
ยท If the target element is greater than the element at the middle index, set the low index to the middle index + 1.
ยท Repeat steps 3-6 until the element is found or it is clear that the element is not present in the array.
Binary Search Algorithm can be implemented in the following two ways
1. Iterative Method
2. Recursive Method
// C program to implement iterative Binary Search
#include <stdio.h>
// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present"
" in array")
: printf("Element is present at "
"index %d",
result);
return 0;}
// C program to implement recursive Binary Search
#include <stdio.h>
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Second hand laptops in minimum price
Comentรกrios