What is the correct way to search for elements using binary search?

Question

IT education

Hello! I am taking an online course on algorithms and I have a problem with the following assignment:

The first line contains an integer n (1≤n≤100000) and an array A[1…n] of n different natural numbers not exceeding 109 in ascending order, the second line contains an integer k (1≤k≤100000) and k natural numbers b1,…,bk, not exceeding 109. For each i from 1 to k, print the index 1≤j≤n for which A[j]=bi, or −1 if there is no such j.

Here is my solution

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int[] A = new int[n+1];
    for (int i=1; i<=n; i++) {
        A[i] = scan.nextInt(); }
    int b = scan.nextInt();
    int[] k = new int[b+1];
    for (int i=1; i<=b; i++) {
        k[i] = scan.nextInt(); }
    for (int s = 1; s<k.length; s++) {
    	System.out.print(find(A, k[s]) + " ");
    }
    
  }
    
    public static int find(int A[], int k) {
    	int i = 1;
    	int r = A.length;
    	while(i<=r) {
    		int m = (i+r)/2;
    		if (A[m] == k) return m;
    		else if (A[m]>k) r = m-1;
    		else if (A[m]<k) r = m+1;
    	}
    	return -1;
    } 
}

But this answer is not accepted. Writes that the time has expired. How can I speed up this program, how can I properly implement this algorithm?

Answer 1

Here it may be more advantageous to do without binary search. If you first sort the second array in Bsort (the first one is already sorted by condition) and at the same time create a Bmap table mapping the sorted array into the original one, then you can simply compare two arrays element by element:

i = 0;
j = 0;
while (i < n && j < k)
    if (A[i] < Bsort[j])
        i++;
    else {
        if (A[i] > Bsort[j])
            Bres[Bmap[j]] = -1;
        else
            Bres[Bmap[j]] = i;
        j++;
    }
}
for (; j < k; j++)
    Bres[Bmap[j]] = -1;

So the complexity will be k*log(k) for sorting and n+k for comparison.

Answer 2

public static int find(int A[], int k) {
    	int i = 1;
    	int r = A.length+1;
    	while (1<r-i) && (A[i]!=k) {
    		int m = (i+r)/2;
    		if (k<A[m]) r=m else i=m;
    	};
    	if (A[i]==k) return i else return -1;
    }

Answer 3

I think that you need to sort both arrays, and start searching from the middle of the second array. The current element of the second array specifies the division of the first array into larger and smaller ones, descending to the left and right parts of the second array, you can search only in the corresponding parts of the first array. Makes sense if the second array is large.

Answer 4

I have a suspicion that with such a check you enter an infinite loop due to the condition
if (A[m]<k) r = m+1;in the case when the difference between i and r is equal to 1, and the number you are looking for is exactly at position r.
In this case, you will again receive m=(i+r)/2=i in the next pass of the loop and the algorithm will loop.
I would suggest rewriting the algorithm so that the index r is always strictly greater than the desired one, i.e. start at (A.length+1) and modify i and r based on the fact that r is always a "non-included" boundary.