public class LinearAndBinarySearchDemo
1: //LinearAndBinarySearchDemo.java
3: import java.util.Scanner;
5: public class LinearAndBinarySearchDemo
6: {
7: private static int linearSearch(int[] numbers, int key, int[] comparisons)
8: {
9: // Added parameter to hold total number of comparisons.
10: comparisons[0] = 0;
12: for (int i = 0; i < numbers.length; i++)
13: {
14: comparisons[0]++;
15: if (numbers[i] == key)
16: {
17: return i;
18: }
19: }
20: return -1; // not found
21: }
23: private static int binarySearch(int[] numbers, int key, int[] comparisons)
24: {
25: // Added parameter to hold total number of comparisons.
26: comparisons[0] = 0;
28: // Variables to hold the low, middle and high indices
29: // of the area being searched. Starts with entire range.
30: int low = 0;
31: int mid = numbers.length / 2;
32: int high = numbers.length - 1;
34: // Loop until "low" passes "high"
35: while (high >= low)
36: {
37: // Calculate the middle index
38: mid = (high + low) / 2;
40: // Cut the range to either the left or right half,
41: // unless numbers[mid] is the key
42: comparisons[0]++;
43: if (numbers[mid] < key)
44: {
45: low = mid + 1;
46: }
47: else if (numbers[mid] > key)
48: {
49: high = mid - 1;
50: }
51: else
52: {
53: return mid;
54: }
55: }
57: return -1; // not found
58: }
60: // Main program to test both search methods
61: public static void main(String[] args)
62: {
63: int[] numbers = { 2, 4, 7, 10, 11, 32, 45, 87 };
64: System.out.print("NUMBERS: ");
65: for (int i = 0; i < numbers.length; i++)
66: {
67: System.out.print(numbers[i] + " ");
68: }
69: System.out.println();
71: Scanner scnr = new Scanner(System.in);
72: System.out.print("Enter an integer value: ");
73: int key = scnr.nextInt();
74: System.out.println();
76: int[] comparisons = new int[1];
77: int keyIndex = linearSearch(numbers, key, comparisons);
78: if (keyIndex == -1)
79: {
80: System.out.printf
81: (
82: "Linear search: %d was not found with %d comparisons.\n",
83: key, comparisons[0]
84: );
85: }
86: else
87: {
88: System.out.printf
89: (
90: "Linear search: Found %d at index %d with %d comparisons.\n",
91: key, keyIndex, comparisons[0]
92: );
93: }
95: keyIndex = binarySearch(numbers, key, comparisons);
96: if (keyIndex == -1)
97: {
98: System.out.printf
99: (
100: "Binary search: %d was not found with %d comparisons.\n",
101: key, comparisons[0]
102: );
103: }
104: else
105: {
106: System.out.printf
107: (
108: "Binary search: Found %d at index %d with %d comparisons.\n",
109: key, keyIndex, comparisons[0]
110: );
111: }
112: }
113: }