862
插入一個整數到一個有序的數組中，並保證該數組是有序的
需求：將一個數插入到一個有續的數組中，插入成功後，還要保證該數組中的數是有序的
思考：
1）、用折半查找法找到這個數在數組中的位置，如果這個數存在數組中，就把這個數插入到這個數所在數組中的位置上就可以了，如果這個數不存在數組中，則返回這個數組中最小下標的值，該下標值就是該數要插入數組中的位置
2）、將這個數插入到指定數組中的位置
/**
* 折半查找法找到一個元素在數組中的下標
* @param arr 數組
* @param key 要查找的元素
* @return 找到則返回元素在數組中的下標，如果沒找到，則返回這個元素在有序數組中的位置
* 如：[1,4,6,7,10,11,15]，查找8在數組中的位置，如果存在則返1，不存在則返回在7這個下標+1的這個位置上，也就是說在返回10所在位置上的下標
*/
public static int arrayIndexOf(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;
}
最後更新：2017-04-02 06:52:18