1. Arrays.binarySearch的简单介绍

Arrays.binarySearch构造函数的简单介绍

1.1 binarySearch(Object[] arr, Object key)

binarySearch(Object[] arr, Object key)

arr:要检索的数组
key:要搜索的值

如果key在数组中，则返回索引值的索引；否则返回-1或者”-“(插入点)。插入点是索引键将要插入数组的哪一点，即第一个大于该键的元素的索引。

1.1.1 技巧

[1] 搜索值不是数组元素，且在数组范围内，从1开始计数，得“ - 插入点索引值”；

[2] 搜索值是数组元素，从0开始计数，得搜索值的索引值；

[3] 搜索值不是数组元素，且大于数组内元素，索引值为 – (length + 1);

[4] 搜索值不是数组元素，且小于数组内元素，索引值为 – 1。

1.1.2 代码

int arrays [] =new int[]{1,3,4,5,8,9};

Arrays.sort(arr);

int a = Arrays.binarySearch(arrays,6);

int b = Arrays.binarySearch(arrays,4);

int c = Arrays.binarySearch(arrays,0);

int d = Arrays.binarySearch(arrays,10);

System.out.println(“a = “+a +”,b = “ +b +”,c = “ + c +”,d = “+d);

结果：a= -5, b = 2, c = -1,d = -7

1.2 binarySearch(Object[] arr, int fromIndex, int toIndex, Object key)

arr：要搜索的数组

fromIndex：指定范围的开始处索引（包含）

toIndex：指定范围的结束处索引（不包含）

key：要搜索的值

如果要搜索的元素key在指定的范围内，则返回搜索值的索引；否则返回-1或“-”（插入点）。

1.2.1 技巧

[1] 该搜索值在范围内，但不是数组元素，由1开始计数，得“ - 插入点索引值”；

[2] 该搜索值在范围内，且是数组元素，由0开始计数，得搜索值的索引值；

[3] 该搜索值不在范围内，且小于范围（数组）内元素，返回–(fromIndex + 1)；

[4] 该搜索值不在范围内，且大于范围（数组）内元素，返回 –(toIndex + 1)。

1.2.2 代码

int arrays [] =new int[]{1,3,4,5,8,9};

System.out.println(arrays.length+1);

Arrays.sort(arrays);

int e = Arrays.binarySearch(arrays,1, 4, 6);

int f = Arrays.binarySearch(arrays,1, 4, 4);

int g = Arrays.binarySearch(arrays,1, 4 ,2);

int h = Arrays.binarySearch(arrays,1, 3, 10);

int i = Arrays.binarySearch(arrays,1, 3, 0);

System.out.println(“e = “+e +”, f= “ +f +”, g= “ + g +”, h= “+h +”, i = “ + i);

结果：e = -5, f = 2,g = -2, h = -4, i = -2

2.最长递增子序列

   /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here23
        if(arr == null || arr.length==0)return arr;
        int max = 0;
        int[] dp = new int[arr.length];
        int[] indexs = new int[arr.length];
        int k = 0;
        for(int i = 0;i<arr.length;i++){
            int index = Arrays.binarySearch(dp,0,k,arr[i]);
            if(index < 0)index = -(index+1);
            dp[index] = arr[i];
            if(index == k){
                k++;
                indexs[i] = k;
            }else indexs[i] = index+1;
            max = Math.max(indexs[i],max);
        }
        int[] res = new int[max];
        for(int i = arr.length-1;i>=0;i--){
            if(indexs[i]==max){
                res[max-1] = arr[i];
                max--;
            }
        }
        return res;
    }  
   /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        if(arr.length <= 1|| arr == null) return arr;
        // 序列
        int[] end = new int[arr.length];
        // 最长子序列的长度len
        int[] indlen = new int[arr.length];
        end[0] = arr[0];
        // 序列的长度
        int len = 1;
        indlen[0] = len;
        for(int i=1; i<arr.length; i++){
            if(end[(len-1)] < arr[i]){
                // 如果大于就放在end后
                end[len++] = arr[i];
                indlen[i] = len;
            }else if(end[len-1] == arr[i]){
                indlen[i] = len;
            }else{
                // 替换第一个大于元素位置
                int index = findFirstIndex(end, len, arr[i]);
                end[index] = arr[i];
                indlen[i] = (index+1);
            }
        }
         
        int[] res = new int[len];
        for(int i=arr.length-1; i>=0; i--){
            if(indlen[i] == len){
                res[--len] = arr[i];
            }
        }
        return res;
    }
     
    public int findFirstIndex(int[] end, int len, int key){
        int left = 0;
        int right = len-1;
        while(left <= right){
            int mid = (left + right)>>1;
            if(end[mid] < key){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        //return end[left]<key ? (left+1):left;
        return left;
    }