Check if a value exists in an Array in Java

To check if a value exists in an array or not in Java, we can follow 2 methods: Linear search and binary search. To use binary search, the array must be sorted.

Time complexity – Linear search: O(n), Binary search: O(log n)

Steps to follow: Linear search

• Traverse through the entire array using any loop and check each and every element of the array with the value to be found.
• If the value to be found got matched to any element in the array then return or print at which index the element is found or else print not found.

public class Main
{
  public static void main(String[] args) {
    int a[]={3,2,4,5,7,6,8};    //declaration and initialization of array
    int value=4;     //suppose value to be found out is 4
    int idx=-1;       //act as one type of flag, it will get updated to index of the value if found or else remain the same which will show weather the value is found or not
    for(int i=0;i<a.length;i++)   //traverse the array
    {
        if(value==a[i])     //checking to each and every element of array with the value to be found out
        {
            idx=i;      //if the value is found than the index of it is stored in idx and idx gets updated from -1 to actual index no. showing element is found out
            break;      //it makes the code efficient by breaking out of loop if value is found without traversing the whole array by providing the first occurrence of the value
        }
    }
    if(idx!=-1)     //checks is idx is get updated to index of value or still the value is -1, if -1 then it's not updated and element is not found
    {
        System.out.print("value found at index "+idx);
    }
    else{
        System.out.print("value not found");
    }
  }
}

Output:

value found at index 2

Steps to follow: Binary search to check if array element exists in that array

1. Make sure the array is sorted, if not then sort it by using sort() of Arrays class of java.util package as Arrays.sort(<array-name>). sort() is the pre-defined static method of Arrays class.
2. If the mid element of the whole array is equal to the target value, it means the target value is found in the array.
3. If the target value to be found is less than the middle of the interval(initially the whole array is the total interval), contract the interval to the left sub array from starting to mid-1 or else contract it to the sub array from mid+1 to last.
   Repeatedly check from the second point until the target value is found or the interval is empty. Interval is said to be empty when the counter from starting and ending, also the mid value will be the same element.
4. We are not returning the index number in binary search because after sorting, the index number got changed for every element with respect to the actually provided array.

   int a[] = {3,2,4,5,7,6,8};
   int l = 0, h = a.length-1, value = 4, mid=0;

   while(l<=h)
   {
      mid = (l+h)/2;
      if(a[mid] == value)
      { 
         System.out.println("Item found");    //It will show item is found
         break;         //to make it efficient
      }
      else if(a[mid]<value)     //if mid value of array is smaller than target value then whole array is reduced to smaller interval from mid+1 to last
      {
         l = mid+1;
      }
      else                        //else return the interval from 0 to mid-1 interval
      { 
         h = mid - 1;
      }
   }

Output:

Item found