Linear search in a sorted array - Java

Question

I want to make a program that searches linear in a sorted array and can output the different positions in which the searched item is found. At the moment my program only outputs the first position in which the search item is found, so here's an example from what what my program does right now:

Enter number of elements
5
Enter 5 integers
1
3
3
9
15
Enter value to find
3
3 is present at location 2.

Now the thing is that 3 is on location 2 and 3, and that's what i want to edit in the program but i don't know how to do it.

Here's the code of my program:

import java.util.Scanner;
 class LinearSearchArray1 {
    public static void main(String args[]){
        int c, n, search, array[];

        Scanner in = new Scanner(System.in);
        System.out.println("Enter number of elements");
        n = in.nextInt(); 
        array = new int[n];

        System.out.println("Enter " + n + " integers");

        for (c = 0; c < n; c++)
        array[c] = in.nextInt();

        System.out.println("Enter value to find");
        search = in.nextInt();

        for (c = 0; c < n; c++)
        {
            if (array[c] == search)     /* Searching element is present */
            {
             System.out.println(search + " is present at location " + (c + 1) + ".");
            break;
        }
    }
    if (c == n)  /* Searching element is absent */
        System.out.println(search + " is not present in array.");
    }
}

Arrays.binarySearch to find the first position. Then loop to find the others - they must be together in a sorted array. — Boris the Spider
– Boris the Spider, Commented Dec 24, 2015 at 12:37

Mohammed Aouf Zouag · Accepted Answer · 2015-12-24 12:43:53Z

2

...
System.out.println("Enter value to find");
search = in.nextInt();

boolean exists = false;

for (c = 0; c < n; c++)
{
  if (array[c] == search)     /* Searching element is present */
  {
     System.out.println(search + " is present at location " + (c + 1) + ".");
     exists = true;
  }
}

if (!exists)  /* Searching element is absent */
  System.out.println(search + " is not present in array.");

You need to delete the break; statement. Otherwise, as soon as the first value is found, the loop is broken, & the next matches would never be reached.

edited Dec 24, 2015 at 12:43

answered Dec 24, 2015 at 12:32

Mohammed Aouf Zouag

17.2k4 gold badges44 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

TinaXx Over a year ago

OMG it was actually that simple, just one problem left: i get "3 is not present in array." in the last line.

Mohammed Aouf Zouag Over a year ago

Actually, you need something like a flag. Check my edit.

Danny_ds Over a year ago

@Sparta This will scan the whole array each time. A break on the next non-equal value would be better, since the array is sorted. (of course, a binary search would be preferred for larger arrays)

Mohammed Aouf Zouag Over a year ago

@Danny_ds you're right, totally missed the sorted fact.

Tamás F · Accepted Answer · 2015-12-24 12:52:39Z

1

This code may work for you.

    int c = 0;

    while (c < array.length && array[c] < search)
    {
        cc++;
    }
    int first = c;
    while (c < array.length && array[c] == search) {
        c++;
    }
    int last = c;

Now elements between index "first" and "last" (including them) contain the searched number. So you basicly search for the first and the last element that are the same as you are looking for.
Example to write it to console:

    for (int i = first; i <= last; i++)
    {
        System.out.println(search + " is present at location " + (i + 1) + ".");
    }

answered Dec 24, 2015 at 12:52

Tamás F

16813 bronze badges

1 Comment

user5639737 Over a year ago

No, the last element does NOT contain the desired value. In fact, last will be outside the array if all elements are less than or equal to search. The code is correct (except for the cc instead of c), and in fact it is exactly what I would have used. However, after the code, what we know is that there are exactly last-first elements matching search (note that this could be zero), and those elements are between first (included) and last (excluded). The last for would work OK if the <= were changed to a <. No iterations in that loop means search is not in the array.

Pang · Accepted Answer · 2017-03-23 09:15:54Z

import java.util.Scanner;

public class BinarySearch {
    /*
     * A binary search or half-interval search algorithm finds the position of a
     * specified value (the input "key") within a sorted array. Binary search
     * requires a sorted collection. Also, binary searching can only be applied
     * to a collection that allows random access (indexing).
     * 
     * Worst case performance: O(log n)
     * 
     * Best case performance: O(1)
     */

    public static int binSearch(int a[], int key) {
        int start = 0;
        int end = a.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;

            if (key == a[mid]) {
                return mid;
            }
            if (key < a[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;

            }

        }
        return -1;

    }

    public static void main(String arg[]) {

        BinarySearch bi = new BinarySearch();
        int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 };
        System.out.println("Please Key to be search");
        Scanner sc = new Scanner(System.in);
        int input = Integer.parseInt(sc.nextLine());

        if (bi.binSearch(arr, input) != -1) {
            System.out.println(input + ": " + " Search found at "
                    + bi.binSearch(arr, input) + " " + "Position");
        } else {
            System.out.println(input + ": " + " Search Result not found ");
        }

    }
}

Avikool91 · Accepted Answer · 2017-11-25 08:35:49Z

Use ArrayList to store the location:-

import java.util.ArrayList; import java.util.Scanner;

class LinearSearchArray1 {

public static void main(String args[]){

    int c, n, search, array[];
    boolean searchStatus=false;

    ArrayList<Integer> al=new ArrayList<Integer>();

    Scanner in = new Scanner(System.in);
    System.out.println("Enter number of elements");
    n = in.nextInt(); 
    array = new int[n];
    System.out.println("Enter " + n + " integers");
    for (c = 0; c < n; c++)
        array[c] = in.nextInt();
    System.out.println("Enter value to find");
    search = in.nextInt();
    for (c = 0; c < n; c++)
    {
        if (array[c] == search)     /* Searching element is present */
        {
         al.add(c+1);
         searchStatus=true;  
    }
}
if (searchStatus==false)  /* Searching element is absent */
    System.out.println(search + " is not present in array.");
else {
    System.out.print(search+ " is present in array at location ");
    for(Integer i:al) 
        System.out.print(i+",");
}
}

}

Ahmed Abubaker · Accepted Answer · 2024-09-30 04:41:54Z

// Java program to implement linear     
//search in a sorted array .

public class SearchingSorted {
   
// Function to implement 
//Search operation       
   static int findElement(int arr[] , int n , int key) {
     for(int i = 0; i< n; i++) {
        if(arr[i]== key) {
            return i;

       }

}


// If element its not found
  return -1;

}

public static void main(String args[]) {
     int arr[] = {5 , 6 , 7 , 8 , 9 , 10};   
     int n = arr.length;     

     // Using a last element as search element .  
     int key = 10;
     
     // Function call .
     int position = find element(arr , n , key);  
      
      if(position == -1) {
           System.out.println("Element is not found ");

          } else {
              System.out.println("Element is at position: " + (position + 1) )
             }     


}



}

Collectives™ on Stack Overflow

Linear search in a sorted array - Java

5 Answers 5

4 Comments

1 Comment

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

4 Comments

1 Comment

Comments

Comments

Comments

Related