Searching Algorithms in Java with Examples

In this article, we show you two basic searching algorithms in Java: Linear Search and Binary Search.

1. Linear Search

Linear search is the simplest search algorithm. It sequentially checks each element of the array until a match is found or the whole array is traversed.

How Linear Search Works?

1. Start from the first element of the array.
2. Compare the current element with the key.
3. If the current element matches the key, return its index.
4. If the key is not found after checking all elements, return -1.

Advantages:

• Simple and easy to implement.
• Works for unsorted or unordered arrays.

Disadvantages:

• Slow for large datasets as it checks every element.
• Time Complexity: O(n) in the worst case (where n is the number of elements).

Linear Search Java Program Example:

package com.javacodepoint.search;

public class LinearSearch {
	
	public static int linearSearch(int[] array, int key) {
		for (int i = 0; i < array.length; i++) {
			if (array[i] == key) {
				return i; // Return the index where the key is found
			}
		}
		return -1; // Return -1 if the key is not found
	}

	public static void main(String[] args) {
		int[] numbers = { 5, 12, 18, 23, 45, 89 };
		int key = 23;

		int result = linearSearch(numbers, key);

		if (result != -1) {
			System.out.println("Element found at index: " + result);
		} else {
			System.out.println("Element not found.");
		}
	}
}

2. Binary Search

Binary Search is a fast and efficient algorithm that works only on sorted arrays. It divides the search range into halves and eliminates one-half in each iteration.

How Binary Search Works?

1. Start by setting two pointers: low (start of the array) and high (end of the array).
2. Calculate the mid index: mid = low + ((high−low) / 2)
3. Compare the key with the element at mid:
   • If the key matches the middle element, return the index.
   • If the key is smaller than the middle element, repeat the search in the left half.
   • If the key is larger, repeat the search in the right half.
4. Repeat the steps until low is greater than high, or the key is found.
5. If not found, return -1.

Advantages:

• Very efficient for large datasets.
• Reduces the problem size by half with each step.
• Time Complexity: O(log⁡n).

Disadvantages:

• Requires the array to be sorted.
• Does not work efficiently for dynamically changing datasets.

Binary Search Java Program Example:

package com.javacodepoint.search;

import java.util.Arrays;

public class BinarySearch {

	public static int binarySearch(int[] array, int key) {
		int low = 0;
		int high = array.length - 1;

		while (low <= high) {
			int mid = low + (high - low) / 2; // Avoids overflow

			if (array[mid] == key) {
				return mid; // Key found at index mid
			} else if (array[mid] < key) {
				low = mid + 1; // Search in the right half
			} else {
				high = mid - 1; // Search in the left half
			}
		}
		return -1; // Key not found
	}

	public static void main(String[] args) {
		int[] numbers = { 3, 8, 15, 20, 27, 35, 50 };
		int key = 20;

		// Ensure the array is sorted
		Arrays.sort(numbers);

		int result = binarySearch(numbers, key);

		if (result != -1) {
			System.out.println("Element found at index: " + result);
		} else {
			System.out.println("Element not found.");
		}
	}
}

Comparison of Linear Search and Binary Search

Conclusion

By understanding these two algorithms, you’ll be well-equipped to handle searching problems in Java!

Use Linear Search when:

• The dataset is small.
• The dataset is unsorted or unordered.
• You need simplicity over speed.

Use Binary Search when:

• The dataset is large.
• The dataset is sorted.