Answer to Question #298985 in Java | JSP | JSF for Bruhh

Question

1. Binary Search

by CodeChum Admin

Searching is one very important Computer Science task. When you have a list, searching is natural. You would want to search for an item in the list. If the list is not sorted, there is no way to it but do a linear search - check each element until the item is found or until there are no elements left to inspect.

More info here, Important!

https://pastebin.com/eZWPNhh9

Answer 1

import java.util.*;


class App {


	public static void main(String[] args) {
		Scanner keyBoard = new Scanner(System.in);


		List<Integer> list = new LinkedList<Integer>();
		int n = keyBoard.nextInt();
		for (int i = 0; i < n; ++i) {
			list.add(keyBoard.nextInt());
		}
		int target = keyBoard.nextInt();
		Collections.sort(list);


		int countIterations = binarySearch(list, target);


		for (int i = 0; i < n; ++i) {
			System.out.print(list.get(i) + " ");
		}
		System.out.println();
		if (countIterations != -1) {
			System.out.println(countIterations + " FOUND");
		} else {
			System.out.println("NOT FOUND");
		}


		keyBoard.close();
	}


	static int binarySearch(List<Integer> list, int number) {
		int first = 0;
		int last = list.size() - 1;
		int middle = (first + last) / 2;
		int counter = 0;
		while (first <= last) {
			if (list.get(middle) < number) {
				counter++;
				first = middle + 1;
			} else if (list.get(middle)== number) {
				counter++;
				return counter;
			} else {
				counter++;
				last = middle - 1;
			}
			
			middle = (first + last) / 2;
		}
		return -1;
	}
}