Java Program to Implement Binary Search in an Array

Introduction

Binary Search is an efficient algorithm for finding an item from a sorted array. The binary search algorithm works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the algorithm narrows the interval to the lower half; otherwise, it narrows it to the upper half. This process continues until the value is found or the interval is empty.

Problem Statement

Create a Java program that:

• Prompts the user to enter the size of a sorted array and its elements.
• Prompts the user to enter the element to search for in the array.
• Implements the binary search algorithm to find the element.
• Displays the index of the element if found or a message indicating that the element is not found.

Example:

• Input:
  • Array: [2, 3, 4, 10, 40]
  • Element to search: 10
• Output: "Element 10 is found at index 3"

Solution Steps

1. Read the Array Size and Elements: Use the Scanner class to take the size and elements of the sorted array as input from the user.
2. Read the Element to Search: Prompt the user to enter the element to search for in the array.
3. Implement Binary Search: Use a loop or recursion to implement the binary search algorithm.
4. Display the Result: Print the index of the element if found or a message indicating that the element is not found.

Java Program

// Java Program to Implement Binary Search in an Array // Author: https://www.rameshfadatare.com/ import java.util.Scanner; public class BinarySearch { public static void main(String[] args) { // Step 1: Read the size and elements of the array from the user Scanner scanner = new Scanner(System.in); System.out.print("Enter the size of the array: "); int size = scanner.nextInt(); int[] array = new int[size]; System.out.println("Enter the elements of the sorted array:"); for (int i = 0; i < size; i++) { array[i] = scanner.nextInt(); } // Step 2: Read the element to search from the user System.out.print("Enter the element to search: "); int key = scanner.nextInt(); // Step 3: Perform binary search int result = binarySearch(array, 0, size - 1, key); // Step 4: Display the result if (result == -1) { System.out.println("Element " + key + " is not found in the array."); } else { System.out.println("Element " + key + " is found at index " + result); } } // Method to perform binary search public static int binarySearch(int[] array, int low, int high, int key) { while (low <= high) { int mid = low + (high - low) / 2; // Find the middle element // Check if the key is present at mid if (array[mid] == key) { return mid; } // If the key is greater, ignore the left half if (array[mid] < key) { low = mid + 1; } // If the key is smaller, ignore the right half else { high = mid - 1; } } // If the element is not present in the array return -1; } } 

Explanation

Step 1: Read the Array Size and Elements

• The Scanner class is used to read the size of the array and its elements. The nextInt() method captures the size and each element. The array should be sorted for binary search to work correctly.

Step 2: Read the Element to Search

• The Scanner class is used to read the element that the user wants to search for in the array.

Step 3: Implement Binary Search

• The binarySearch() method is implemented to perform binary search:
  • The method takes the array, the low index, the high index, and the key as input.
  • It calculates the middle index and compares the middle element with the key.
  • If the middle element is equal to the key, it returns the index.
  • If the key is greater than the middle element, it searches in the right half; otherwise, it searches in the left half.
  • If the key is not found, it returns -1.

Step 4: Display the Result

• The program prints the index of the element if found, or it displays a message indicating that the element is not found.

Output Example

Example 1:

Enter the size of the array: 5 Enter the elements of the sorted array: 2 3 4 10 40 Enter the element to search: 10 Element 10 is found at index 3 

Example 2:

Enter the size of the array: 5 Enter the elements of the sorted array: 2 3 4 10 40 Enter the element to search: 5 Element 5 is not found in the array. 

Conclusion

This Java program demonstrates how to implement the binary search algorithm to find an element in a sorted array. It covers essential concepts such as array manipulation, conditional logic, and efficient search techniques, making it a valuable exercise for beginners learning Java programming.