黑马程序员技术交流社区

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

---

作者: lockwood    时间: 2015-5-2 23:01
标题: 想要将一个元素插入到该数组中，还要保证该数组是有序的
练习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;
                        }

---

作者: 大西洋    时间: 2015-5-3 00:25
貌似用Set集合的TreeSet可以有序存放~ :)

---

作者: 下一页5    时间: 2015-5-3 00:27
我只记得-1改成min

---

作者: lockwood    时间: 2015-5-3 07:48

大西洋 发表于 2015-5-3 00:25
貌似用Set集合的TreeSet可以有序存放~

还没学set集合哟～～～亲

---

作者: lockwood    时间: 2015-5-3 07:51

下一页5 发表于 2015-5-3 00:27
我只记得-1改成min

索嘎！！带斯奈

---

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

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