有关JAVA二分法的算法

Question

给出两个数组，用二分法算出两个数组的交集，大家帮忙想想怎么写这个代码。谢谢各位

Answer 1

这两个数组都是INT类型的数组，大家帮忙想想怎么写，我不大会写楼上的帮忙给写出来吧，在这里不胜感激

Answer 2

package com.book.java2;import java.util.ArrayList;
import java.util.List;public class Intersection { /**
 * @param a
 * @param b
 *            递增有序数组
 * @return a和b数组的交集
 */
public List<String> getIntersection(String[] a, String[] b) {
List<String> list = new ArrayList<String>(); if (a.length == 0 || b.length == 0) {
return null;
} for (String str : a) {
int low = 0;
int high = b.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (str.compareTo(b[mid]) < 0) {
high = mid - 1;
} else if (str.compareTo(b[mid]) > 0) {
low = mid + 1;
} else {
list.add(str);
break;
}
}
} return list;
}
}

Answer 3

import java.util.*;
public class Intersection{
    public static void main(String[] args){
         int[] a={2,3,7,10,15,20,25,26};  //假设a,b数组都已经排好序了,如果没有排序,可以用Arrays.sort()方法对其排序.
         int[] b={2,3,5,7,8,20,26};
         int[] c=new int[a.length];
         int count=0;
         for(int i=0;i<b.length;i++){
            if(binarySearch(a,b[i])>=0){
               c[count++]=b[i];
            }
         }
         System.out.println("a数组:"+Arrays.toString(a));
         System.out.println("b数组:"+Arrays.toString(b));
         System.out.print("交集:[");
         for(int i=0;i<count;i++){
            System.out.print(c[i]+", ");
         }
         System.out.println("]");
    }
    
    static int binarySearch(int[] array,int elem){  //二分法查找elem在array数组中的位置,找不到返回-1
       int left=0,right=array.length-1,mid;
       while(left<=right){
           mid=(left+right)/2;
           if(elem>array[mid]){
              left=mid+1;
           }else if(elem<array[mid]){
              right=mid-1;
           }else{
              return mid;
           }
        }
        return -1;
     }

Answer 4

main方法最后的那条语句,改为下面的语句,可以退两格打印出']',这样就可以把输出交集后最后的逗号去掉了.
System.out.println("\b\b]");

Answer 5

package com.example.thread;import java.util.Arrays;public class t { public static void main(String[] args){
        int[] a={80,45,7,10,20,15,25,26};  //假设a,b数组都已经排好序了,如果没有排序,可以用Arrays.sort()方法对其排序.
        int[] b={2,26,5,7,45,20,26};
        Arrays.sort(a);
        Arrays.sort(b);
        int[] c=new int[a.length];
        int count=0;
        for(int i=0;i<b.length;i++){
           if(binarySearch(a,b[i])>=0){
              c[count++]=b[i];
           }
        }
        System.out.println("a数组:"+Arrays.toString(a));
        //System.out.println("a数组:"+Arrays.sort(a));        
        System.out.println("b数组:"+Arrays.toString(b));
        System.out.print("交集:[");
        for(int i=0;i<count;i++){
           System.out.print(c[i]+", ");
        }
        System.out.println("\b\b]");
   }
   
   static int binarySearch(int[] array,int elem){  //二分法查找elem在array数组中的位置,找不到返回-1
      int left=0,right=array.length-1,mid;
      while(left<=right){
          mid=(left+right)/2;
          if(elem>array[mid]){
             left=mid+1;
          }else if(elem<array[mid]){
             right=mid-1;
          }else{
             return mid;
          }
       }
       return -1;
    }
}