Searching:
-->Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.
-->In Java,searching refers to the process of finding an element in a data structure like an array,list,or map.
--> Based on the type of search operation, these algorithms are generally classified into two categories.
- Linear Search(Sequential Search)
- Binary Search(Interval Search)
Linear Search:
--> Linear search is a fundamental search algorithm that iterates through a list of elements one by one, comparing each element to the target value.
--> If the target value is found, the search stops and returns the index of the element.
--> Otherwise, the search continues until the end of the list is reached, at which point it returns -1 to indicate that the target value was not found.
When is Linear Search Useful?
Linear search is useful in several scenarios:
1. Small Data Sets
--->When the data set is relatively small (e.g., less than a few hundred elements), linear search can be efficient because the number of comparisons required is small.
2. Unsorted Data
-->Linear search is particularly useful for unsorted data, as it does not require any prior sorting of the elements.
3. Simple Implementation
-->Linear search is one of the simplest search algorithms to implement, making it suitable for beginners and educational purposes.
4. Iterative Nature
-->Linear search is an iterative algorithm, meaning it can be easily implemented using a loop. This makes it easy to understand and debug.
5. Real-Time Applications
-->In certain real-time applications where the data set is constantly changing, linear search can be more efficient than other search algorithms that require preprocessing or sorting.
6. Limited Memory
-->Linear search requires minimal memory overhead, as it only needs to store the current element being compared. This makes it suitable for systems with limited memory resources.
Example Program:(using while loop)
package Search;
public class LinearSearch {
public static void main(String[] args)
{
int[] arr= {12,34,76,56,87,45,100};
int key=87;
int i =0;
while(true)
{
if (arr[i]==key)
{
System.out.println("key "+key+" is presenting at:"+i );
return;// Exits the main() method immediately
}
i++;
}
System.out.println("Key " + key + " is not found in the array.");
}
}
Output:
key 87 is presenting at:4
2.
package Search;
public class LinearSearch {
public static void main(String[] args) {
int[] arr = {12, 34, 76, 56, 87, 45, 100};
int key = 87;
int i = 0;
while (i < arr.length) {
if (arr[i] == key) {
System.out.println("Key " + key + " is present at index: " + i);
break;// Exits only the loop, but the program continues
}
i++;
}
System.out.println("Search operation complete.");
}
}
Output:
Key 87 is present at index: 4
Search operation complete.
Note:
Why Use return; Instead of break;?
-->return; exits the entire method (main() in this case).
-->break; only exits the loop, but execution would continue with any remaining statements after the loop.
Recursive Approach:
package Search;
public class RecursiveLinearSearch
{
public static void main(String[] args) {
int[] arr = {12, 34, 76, 56, 87, 45, 100};
int key = 100;
int result = linearSearch(arr, key, 0);
if (result != -1) {
System.out.println("Key " + key + " is present at index: " + result);
} else {
System.out.println("Key " + key + " is not found in the array.");
}
}
public static int linearSearch(int[] arr, int key, int index)
{
if (index >= arr.length)
{
return -1;
}
if (arr[index] == key)
{
return index;
}
return linearSearch(arr, key, index + 1);
}
}
Output:
Key 100 is present at index: 6
Top comments (0)