Answer to Question #302395 in Java | JSP | JSF for Akash srivastava

Question

Searching an element in a sorted array

standard input/output: 2s/128000 kB

Given a sorted array arr[] of N integers and a number K is given. The task is to check if the element K is present in the array or not.

Note: Use binary search to solve the problem

Input

The first line of input contains a number of test cases T. For each test case, first line of input contains a number of elements in the array, and the number K separated by space. The next line contains N elements.

Constraints:

1 <= T <= 10

1 <= N <= 100000

1 <= K <= 1000000000

1 <= arr[i] <= 1000000000

Sum of N over all test cases doesn't exceed 10⁶

Output

For each testcase, if the element is present in the array print "1" (without quotes), else print "-1" (without quotes).

Answer 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] array = new int[n];
            for (int j = 0; j < n; j++) {
                array[j] = in.nextInt();
            }
            int left = 0;
            int right = array.length - 1;
            int middle = (left + right) / 2;
            int find = -1;
            while (left <= right) {
                if (array[middle] == k) {
                    find = 1;
                    break;
                } else if (array[middle] > k) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
                middle = (left + right) / 2;
            }
            System.out.println(find);
        }
    }
}