JetBrains Academy: Binary search in Java

Find a fixed point in an array:

Write a program to check a sorted array of various ints contains a fixed point. The array is sorted in the ascending order.

A fixed point is an index i such A[i] = i.

The integers in the array can be negative. The input array doesn't contain duplicates.

Use binary search to solve the problem.

Input data format:
The first line contains a number of elements in the array, the second one consists of the elements.

Output data format:
The program should output "true" or "false".

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int leftBorder = 0;
        int rightBorder = Integer.parseInt(scanner.nextLine());
        
        int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
                            .mapToInt(Integer::parseInt)
                            .toArray();
                            
        System.out.println(containsFixedPoint(array, leftBorder, rightBorder));
    }
    
    public static boolean containsFixedPoint(int[] array, int leftBorder, int rightBorder) {
        if (leftBorder > rightBorder) {
            return false;
        }

        int mid = leftBorder + (rightBorder - leftBorder) / 2;

        if (mid == array[mid]) {
            return true;
        } else if (mid < array[mid]) {
            return containsFixedPoint(array, leftBorder, mid - 1);
        } else {
            return containsFixedPoint(array, mid + 1, rightBorder);
        }
    }
}

Search in a descending ordered array:

Given a method that implements the binary search algorithm. It searches in ascending sorted arrays.

You should modify the method:

it should search in descending sorted arrays instead of ascending ones;
it should return the first index of the target element from the beginning of the array, i.e. the leftmost index.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    /* Modify this method */
    public static int binarySearch(int elem, int[] array) {

        int left = 0;
        int right = array.length - 1;
        int index = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (elem == array[mid]) {
                index = mid;
                right = mid - 1;
            } else if (elem < array[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return index;
    }

    /* Do not change code below */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int elem = scanner.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        while (scanner.hasNextInt()) {
            list.add(scanner.nextInt());
        }
        int[] array = new int[list.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }
        System.out.println(binarySearch(elem, array));
    }
}

Find array elements in another array:

The first line contains integer 1 ≤ n ≤ 10⁵. The second one contains of an array A[1…n] of n various natural numbers, not exceeding 10⁹, in ascending order.

The third line contains integer 1 ≤ k ≤ 10⁵. The fourth one consists of k natural numbers b₁, ... , b_k , not exceeding 10⁹.

For each i from 1 to k it is necessary to output index 1 ≤ j ≤ n, for which A[j]=b_i, or −1, if there is no such j.

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    
    int arrayLength = Integer.parseInt(scanner.nextLine());
    int[] sortedArray = Arrays.stream(scanner.nextLine().split("\\s+"))
                              .mapToInt(Integer::parseInt)
                              .toArray();
                              
    int amountOfNumbers = Integer.parseInt(scanner.nextLine());
    int[] numbers = Arrays.stream(scanner.nextLine().split("\\s+"))
                          .mapToInt(Integer::parseInt)
                          .toArray();
    
    final String result = Arrays.toString(findIndexesInTheArray(sortedArray, numbers))
                                .replace(", ", " ")
                                .replace("[", "")
                                .replace("]", "");
    System.out.println(result);
  }
  
  public static int[] findIndexesInTheArray(int[] array, int[]numbers) {
    int[] occurrences = new int[numbers.length];

    for (int i = 0; i < numbers.length; i++) {
      int value = numbers[i];

      occurrences[i] = binarySearchShifted(value, array);
    }

    return occurrences;
  }
  
  public static int binarySearchShifted(int elem, int[] array) {
    int shift = 1;
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
      int mid = left + (right - left) / 2;

      if (elem == array[mid]) {
        return mid + shift;
      } else if (elem < array[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
      
    }
    return -1;
  }
  
}

JetBrains Academy: Binary search in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Binary search in Java

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️