二分查找有序数组并插入（不能解决TopK问题）

需求：将一个数插入（替换原来的数）到一个有续的数组中，插入成功后，还要保证该数组中的数是有序的

思考：

1）、用二分查找法找到这个数在数组中的位置：
         位置的可能情况：
         index 最小：0
         index 最大：数组的长度
         index 在数组中：放入后该位置比上一个数大，比下一个数小。

时间复杂度：O（logN）

2）TopK：找到位置后，插入数据，然后后面的数整体向后移动一位（假设为找出最小的K个）。这比方法当K的值较大的时候，也是非常耗时的。对于这种问题，效率比较高的解决方法是使用最小堆。

public class Search_Binary {

    /**
     * 二分查找法：找到一个元素在数组中的下标
     * @param arr 数组
     * @param key 要插入的元素
     * @return 
     * 如：
     * arr =  [1, 4, 6, 7, 10, 11, 15] 
     *    查找7: 返回 3 
     *    查找8：返回 4
     *    查找-1:返回 0 
     *    查找16:返回 7 (越界)
     */
    public int binarySearchIndex(int[] array,int key) {
        int min,max,mid;
        min = 0;
        max = array.length - 1;
        
        while(min <= max) {
            
            mid = (min + max) >> 1;
        
            if (key > array[mid]) {
                min = mid + 1;
            } else if (key < array[mid]) {
                max = mid - 1;
            } else {
                return mid;
            }
        }
        return min;
    }
    
    @Test
    public void testcases() {
        int[] arr = new int[] {1, 4, 6, 7, 10, 11, 15};
        
        System.out.println(binarySearchIndex(arr, 7)); // 3
        
        System.out.println(binarySearchIndex(arr, 8)); // 4
        
        System.out.println(binarySearchIndex(arr, -3)); // 0
        
        System.out.println(binarySearchIndex(arr, 26)); // 7 （越界）
    }
}

-