# Chapter5: Linear Search

### **About Linear search**

* Linear search is a simple searching algorithm that iterates through a collection (such as an array or list) to find a specific element. Here's a short example of linear search in Java.
    
* It's straightforward but not the most efficient for large data sets. It has a time complexity of O(n) where "n" is the number of elements in the list.
    

### **Code using Linear Search algorithm in 1D array**

```java
import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int data=sc.nextInt();
        int[] arr=new int[6];
        for(int i=0; i<arr.length; i++){
            arr[i]=sc.nextInt();
        }
        System.out.print(linearSearch(arr, data));
    }
    static Integer linearSearch(int[] arr, int data){
        if(arr.length==0){
            return -1;
        }
        for(int i=0; i<arr.length; i++){
            if(arr[i]==data){
                return i;
            }
        }
        return -1;
    }
}
```

In this example, the `linearSearch` method takes an array and a target value as parameters. It iterates through the array, comparing each element with the target value. If a match is found, it returns the index of the target element; otherwise, it returns -1 to indicate that the element is not present in the array. The `main` method demonstrates how to use the `linearSearch` method to find a target element in an array.

### **Code using Linear Search algorithm in 2D array**

```java
import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int data=sc.nextInt();
        int[][] arr=new int[3][3];
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                arr[i][j]=sc.nextInt();
            }
        }
        System.out.print(Arrays.toString(search(arr,data)));
    }
    static int[] search(int[][] arr, int data){
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(arr[i][j]==data){
                    return new int[]{i,j};
                }
            }
     }
        return new int[]{-1};
     }
}
```

### **Code using Linear Search algorithm in String**

```java
import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        char data=sc.next().charAt(0);//target input as single character
        System.out.print(stringLinear(s,data));
    }
    static boolean stringLinear(String s, char data){
        if(s.length()==0){
            return false;
        }
        for(int i=0; i<s.length(); i++){
            if(data==s.charAt(i)){//converts the string into characterArray
                return true;
            }
        }
        return false;
    }
}
```

### **LeetCode-no 1295. Find numbers with even number of digits**

https://leetcode.com/problems/find-numbers-with-even-number-of-digits/

* Given an array `nums` of integers, return how many of them contain an **even number** of digits.
    

Example:

My code is attached below

```java
Input: nums = [12,345,2,6,7896]
  Output: 2
  Explanation: 
  12 contains 2 digits (even number of digits). 
  345 contains 3 digits (odd number of digits). 
  2 contains 1 digit (odd number of digits). 
  6 contains 1 digit (odd number of digits). 
  7896 contains 4 digits (even number of digits). 
  Therefore only 12 and 7896 contain an even number of digits.
```

```java
class Solution {
    public int findNumbers(int[] nums) {
        int c=0;
        for(int num:nums){
            if(even(num)%2==0){
                c++;
            }
        }
        return c;
    }
    public int even(int num){
        int digit=(int)(Math.log10(num))+1;//gives the total number of digits in a number
        return digit;
    }
}
```

### **LeetCode-no 1672. Richest Customer Wealth**

[https://leetcode.com/problems/richest-customer-wealth/](https://leetcode.com/problems/richest-customer-wealth/)

* You are given an `m x n` integer grid `accounts` where `accounts[i][j]` is the amount of money the `i​​​​​<sup>​​​​​​th</sup>​​​​` customer has in the `j​​​​​<sup>​​​​​​th</sup>`​​​​ bank. Return *the* **wealth** *that the richest customer has.*
    
* A customer's **wealth** is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum **wealth**.
    
    Example:
    

My code is attached below:

```java
Input: accounts = [[1,2,3],[3,2,1]]
  Output: 6
  Explanation:
  1st customer has wealth = 1 + 2 + 3 = 6
  2nd customer has wealth = 3 + 2 + 1 = 6
  Both customers are considered the richest with a wealth of 6 each, so return 6.
```

```java
class Solution {
    public int maximumWealth(int[][] accounts) {
        
        int max=Integer.MIN_VALUE;
        for(int i=0; i<accounts.length; i++){
            int s=0;
            for(int j=0; j<accounts[i].length; j++){
                s+=accounts[i][j];
            }
            if(max<s){
                max=s;
            }
        }
        return max;
    }
}
```

### **Note**

* The `linearSearch` function takes an array (`arr`) and a target value to search for.
    
* It iterates through the array using a `for` loop and compares each element with the target value.
    
* If a match is found, it returns the index of the element; otherwise, it returns -1 to indicate that the target is not in the array.
    
* In the `main` method, we demonstrate how to use the `linearSearch` function.
    

### **Performance**

* Linear search has a time complexity of O(n), meaning its execution time increases linearly with the size of the input array. For larger data sets, more efficient algorithms like binary search may be preferred.
    
* Best case -&gt; element found at 0th position of array itself -&gt; O(1)
    
* Worst case -&gt; element not found in array -&gt; O(n)
    

### **Conclusion**

Remember that linear search is not the most efficient search algorithm for large data sets, but it can be a good choice for smaller arrays or when simplicity is more important than speed. Stay tuned to explore more with me. Cheers to all, Happy coding!!