Binary Search

/*
 * Problem : Process an array and a number k.
 * Input   : n, then n integers, then k.
 * Output  : The index or -1.
 * Approach: Halve the search area.
 * Time    : O(log n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a, int k) {
        // Step 1: The search area is a[low..high]. At the start it is the whole array.
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            // Step 2: Look at the middle element. This form of mid can not overflow.
            int mid = low + (high - low) / 2;

            if (a[mid] == k) {
                // Step 3: Found it.
                return mid;
            } else if (a[mid] < k) {
                // Step 4: The target is bigger, so it can only be on the right side.
                low = mid + 1;
            } else {
                // Step 5: The target is smaller, so it can only be on the left side.
                high = mid - 1;
            }
        }

        // Step 6: The search area is empty. The target is not in the array.
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}