练习2：有一个有序 的数组，想要将一个元素插入到该数组中，还要保证该数组是有序的。
{1, 7, 3, 7, 3, 9, 3, 55, 22, 43} 例如将8 放入下列数组中，并且放入后，该数组还是有序的。
*/
class halfSearch {
public static void main(String[] args) {
int[] arr = {1, 7, 3, 7, 3, 9, 3, 55, 22, 43};
int index = halfSearch_2(arr,9);
System.out.println("index=" + index);
}
public static int halfSearch(int[] arr, int key) {
int min, max, mid;
min = 0;
max = arr.length - 1;
mid = (max + min) / 2;
while(arr[mid] != key) {
if(key > arr[mid]) {
min = mid + 1;
}
else if(key < arr[mid]){
max = mid - 1;
}
if(min > max) {
return -1;
}
mid = (max + min) / 2;
}
return mid;
}
//折半的另外一种思考方式，用折半不等于key 的方式来完成，如下,只要min《=max就能折半。
public static int halfSearch_2(int[] arr, int key) {
int min = 0, max = arr.length - 1, mid;
while (min <= max) {
mid = (max + min) >> 1;
if (key > arr[mid]) {
min = mid + 1;
}
else if (key < arr[mid]) {
max = mid - 1;
}
else {
return mid;
}
}
return -1;
}
/插入一个数并且保证依然是有序的
public static int halfSearch_3(int[] arr, int key) {
int min = 0, max = arr.length - 1, mid;
while (min <= max) {
mid = (max + min) >> 1;
if (key > arr[mid]) {
min = mid + 1;
}
else if (key < arr[mid]) {
max = mid - 1;
}
else {
return mid;
} |
|
收藏
淘帖
踩
