binary search,linear search

Java Program for Linear Search

In the world of computer science, searching algorithms are fundamental techniques for retrieving information from data structures. One of the simplest and most intuitive searching algorithms is the linear search. Linear search is used to search a key element from multiple elements. Linear search is less used today because it is slower than binary search and hashing.

Linear search, also known as sequential search, is a straightforward method for finding an element within a list. It checks each element of the list sequentially until it finds a match or reaches the end of the list. This method is best suited for small or unsorted datasets where the overhead of more complex algorithms isn't justified.

Algorithm for Linear Search

Step 1: Traverse over the array.

Step 2: Match the key element with array element.

Step 3: If key element is found, return the index position of the array element.

Step 4: If key element is not found, return -1.

    public class LinearSearchExample{    
    public static int linearSearch(int[] arr, int key){    
            for(int i=0;i<arr.length;i++){    
                if(arr[i] == key){    
                    return i;    
                }    
            }    
            return -1;    
        }    
        public static void main(String a[]){    
            int[] a1= {10,20,30,50,70,90};    
            int key = 50;    
            System.out.println(key+" is found at index: "+linearSearch(a1, key));    
        }    
    }    

Output:

50 is found at index: 3

Advantages

Simplicity: It is easy to understand and implement.

No Preprocessing: It does not require the data to be sorted.

Versatility: It can be used on any type of data structure (arrays, linked lists, etc.).

Disadvantages

Inefficiency: On average, it requires checking half of the elements (O(n/2)) and, in the worst case, all elements (O(n)).

Not Suitable for Large Datasets: It becomes impractical as the size of the dataset increases.

Performance Analysis

Time Complexity

The time complexity of linear search is O(n), where n is the number of elements in the array. Because in the worst-case scenario, the algorithm has to check every element once.

Space Complexity

The space complexity is O(1) because the algorithm uses a constant amount of additional space, regardless of the input size.

Best Case

The best-case time complexity is O(1) that occurs when the target element is at the first position in the array.

reference:https://www.tpointtech.com/linear-search-in-java

PROGRAM:

package afterfeb13;

public class linearsearch {
    public static void main(String[] args) {
        int[]score= {80,90,70,77,66,55,88,99,102,150};
        int key=150;
        for(int i=0;i<score.length;i++)
        {
            if(score[i]==key)
            {
                System.out.println("key "+score[i]+" present "+" at index "+" "+i);
            }


        }

    }



}

OUTPUT:key 150 present at index 9

Binary Search in Java

Binary search is one of the searching techniques applied when the input is sorted here we are focusing on finding the middle element that acts as a reference frame whether to go left or right to it as the elements are already sorted. This searching helps in optimizing the search technique with every iteration is referred to as binary search and readers do stress over it as it is indirectly applied in solving questions.

Binary Search Algorithm in Java

Below is the Algorithm designed for Binary Search:

1.Start
2.Take input array and Target
3.Initialise start = 0 and end = (array size -1)
4.Intialise mid variable
5.mid = (start+end)/2
6.if array[ mid ] == target then return mid
7.if array[ mid ] < target then start = mid+1
8.if array[ mid ] > target then end = mid-1
9.if start<=end then goto step 5
10.return -1 as Not element found
11.Exit

Reference:https://www.geeksforgeeks.org/binary-search-in-java/

WITHOUTRETUNR PROGRAM EX

package afterfeb13;

public class binarysearch {
    public static void main(String[] args) {
        int[] days = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
        int key = 14;// this for num less--->3
        int min_index = 0;
        int max_index = days.length - 1;
        while (min_index <= max_index) {
            int mid_index = (min_index + max_index) / 2;// 0+14/2=7 //8+14/2=23/2= 11 //12+14/2---26/2 =13
            // this for num less---> 0+14/2=7//0+6/2=3//0+1/2=0.5==1

            if (days[mid_index] == key) // indx=7 num 8==15 //indx=11 num 12==15// indx=14 num 15
            // this for num less--->if nu less indx=7 num 8==3 //4==3//2==3//
            {
                System.out.println("key " + key + " is present at position " + mid_index);
                break;
            } else if (key > days[mid_index])// 15>8//15>11 //15>12
            {
                min_index = mid_index + 1;// 7+1//11+1
                // this for num less--->1+1=2
            }

            else //
            {
                max_index = mid_index - 1;// this for num less---> 7-1//2-1
            }
        }

        if (min_index > max_index)
            System.out.println("search key not found");

    }

}

OUTPUT:

key 14 is present at position 13