import java.util.Scanner;
class BinarySearch {
public static void main(String args[]) {
int c, first, last, middle, 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();
first = 0;
last = n - 1;
middle = (first + last) / 2;
while (first <= last) {
if (array[middle] < search) {
first = middle + 1;
} else if (array[middle] == search) {
System.out.println(search + " found at location " + (middle + 1));
break;
} else {
last = middle - 1;
}
middle = (first + last) / 2;
}
if (first > last) {
System.out.println(search + " is not present in the list.\n");
}
}
}Explanation of the Binary Search Program:
This program demonstrates Binary Search for efficiently finding a given value in a sorted array.
1. Import Scanner Class:
import java.util.Scanner;
The Scanner class is imported to read user input from the console.
2. Class Declaration:
class BinarySearch
The program is within a class called BinarySearch.
3. Main Method:
public static void main(String args[])
A main method is where the program starts to execute.
4. Declare Variables:
int c, first, last, middle, n, search, array[];
- c: The loop counter for stepping through the array.
- first: Index of first element to look at.
- last: Index of last element to look at.
- middle: The index of middle element in array.
- n: Size of the array.
- search: The number the user wants to find in the array.
- array[]: The array where the user’s integers will be stored.
5. Create Scanner Object:
Scanner in = new Scanner(System.in);
A Scanner object is created to read the input from the console.
6. Prompt Number of Elements for Array:
System.out.print(“Enter number of elements”);
n = in.nextInt();
This program prompts the user to enter the number of elements that the array will hold.
7. Declaring the Array:
array = new int [n];
An array array of type int and size n is declared to hold the user integers.
8. Input Array Elements:
System.out.println(“Enter ” + n + ” integers”);
for (c = 0; c < n; c++) array[c] = in.nextInt();
Prompts the user to input n integers and stores them in the array[]. The for loop, from 0 to n-1, accepts and assigns each integer into the array.
9. Input the Search Element:
System.out.println(“Enter value to find”);
search = in.nextInt();
The program prompts the user to enter the number they are looking for in the array (search).
10. Initialize Binary Search Values:
first = 0;
last = n – 1;
middle = (first + last) / 2;
- first is assigned the value 0 that corresponds to the first index of the array
- last is initialized to n – 1 (last index of the array).
- middle is calculated as the average of first and last indices to point to the middle of the array.
11. Binary Search Algorithm:
while (first <= last)
{
if (array[middle] < search
first = middle + 1;
else if (array[middle] == search)
{
System.out.println(search + ” found at location ” + (middle + 1));
break;
}
else
last = middle – 1;
middle = (first + last) / 2;
}
- The while loop runs as long as first <= last, i.e., the search space is valid.
- If the element at middle is smaller than the search, then the search is on the right side of the array. Therefore, first is set to middle + 1.
- If the element at middle equals the search, then the search is successful and the program prints the location of the search and break out of the loop.
- When the element at middle is more significant than search value then the search value will be at left side. Update the last as middle – 1.
- Recalculate the middle on every iteration basis after updating first and last.
12. Manage the Situation of the Element if Not Present
if (first > last)
System.out.println(search + ” is not present in the list.”);
If the first index becomes greater than the last index, it means the search value is not present in the array. In this case, the program outputs that the search value is not found.
Example Outputs:
Case 1: Element Found
Enter number of elements
5
Enter 5 integers
10 20 30 40 50
Enter value to find
30
30 found at location 3
Output Interpretation:
1. User had introduced 5 integers 10 20 30 40 50.
2. The search item was 30.
3. Binary Search Algorithm searched 30 on 3rd location in terms of index being (1 based) and display : 30 found at location 3.
Case 2: Element Not Present
Enter number of elements
5
Enter 5 integers
10 20 30 40 50
Enter value to find
60
60 is not in the list.
Explanation of the Output:
1. The user has input 5 integers: 10 20 30 40 50.
2. The user is looking for 60.
3. The binary search algorithm could not find 60 in the array and prints: 60 is not present in the list.
Conclusion:
This program illustrates Binary Search, a very efficient search algorithm that applies to a sorted array. It repeatedly divides the search space in half, making it much faster than linear search for large datasets. The program takes the array size, elements, and the elements to search using user input, and then it outputs either the index of the element if it existed or a message indicating that it is not present.