黑马程序员技术交流社区

标题: 有一个有序 的数组，想要将一个元素插入到该数组中，还... [打印本页]

---

作者: lockwood    时间: 2015-4-28 23:04
标题: 有一个有序 的数组，想要将一个元素插入到该数组中，还...
看了毕老师的课程以后，编写了一个程序，用于讲一个数插入到一个有序数组中，并且保证该数组仍然有序。
——————————————————下面是代码——————————————————————————————
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;
                        }
                }
                return min;
        }


}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2