A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黑马连家华 中级黑马   /  2012-3-27 18:09  /  1559 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

/*
折半查找数组中是否有4
{1,4,7,3,8,9,0,4,2}
*/

class HalfSearch
{
        public static void arraySort(int[] arr)
        {
                for (int x = 0;x < arr.length-1 ; x++)
                {
                        for (int y = x+1;y < arr.length ;y++ )
                        {
                                if (arr[x] > arr[y])
                                {
                                        int temp = arr[x];
                                        arr[x] = arr[y];
                                        arr[y] = temp;
                                }
                        }
                }
        }
        public static int halfSearch(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid;
                while (min <= max)
                {
                        mid = (min + max)>>1;
                        if (key < arr[mid])
                        {
                                min = mid +1;
                        }
                        else if (key > arr[mid])
                        {
                                max = mid -1;
                        }
                        else
                                return min;
                }
                return -1;
        }
        public static void main(String[] args)
        {
                int[] array = {1,4,7,3,8,9,0,4,2};
                arraySort(array);
                int x = halfSearch(array,9);
                if (x != -1 )
                {
                        System.out.println("此值存在于排序后数组中的["+x+"]位置");
                }
                else
                        System.out.println("数组中不存在此数");
        }
}



到底哪里错了...气死我了

4 个回复

倒序浏览
将key < arr[mid]改为key > arr[mid]
key > arr[mid]改为key < arr[mid]

或者互换min = mid +1;和max = mid -1;

评分

参与人数 1技术分 +1 收起 理由
房宝彬 + 1

查看全部评分

回复 使用道具 举报

public class BinarySelect {

        /**
         * @param args
         */
        public static void main(String[] args) {
        int[] array = {1,4,7,3,8,9,0,4,2};
        
        HalfSearch.arraySort(array);
        
        for(int i=0;i<array.length;i++)
        System.out.println(array[i]);
        
         int x= HalfSearch.halfSearch(array, 1);
         
        if (x != -1 )
        {
                System.out.println("此值存在于排序后数组中的["+x+"]位置");
        }
        else
                System.out.println("数组中不存在此数");

        }

}


class HalfSearch
{
        public static void arraySort(int[] arr)
        {
                for (int x = 0;x < arr.length-1 ; x++)
                {
                        for (int y = x+1;y < arr.length ;y++ )
                        {
                                if (arr[x] > arr[y])
                                {
                                        int temp = arr[x];
                                        arr[x] = arr[y];
                                        arr[y] = temp;
                                }
                        }
                }
        }
        public static int halfSearch(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid;
                while (min <= max)
                {
                        mid = (min + max)/2;
                        if (key < arr[mid])
                        {
              
                                max = mid -1;
                        }
                        else if (key > arr[mid])
                        {
                                min = mid +1;
                        }
                        else{
                                return mid;
                        }
                }
                return -1;
        }
}

你的算法哪里有问题,具体的你看一下我给你修改后的代码吧!
回复 使用道具 举报

public class BinarySelect {

        /**
         * @param args
         */
        public static void main(String[] args) {
        int[] array = {1,4,7,3,8,9,0,4,2};
        
        HalfSearch.arraySort(array);
        
        for(int i=0;i<array.length;i++)
        System.out.println(array[i]);
        
         int x= HalfSearch.halfSearch(array, 1);
         
        if (x != -1 )
        {
                System.out.println("此值存在于排序后数组中的["+x+"]位置");
        }
        else
                System.out.println("数组中不存在此数");

        }

}


class HalfSearch
{
        public static void arraySort(int[] arr)
        {
                for (int x = 0;x < arr.length-1 ; x++)
                {
                        for (int y = x+1;y < arr.length ;y++ )
                        {
                                if (arr[x] > arr[y])
                                {
                                        int temp = arr[x];
                                        arr[x] = arr[y];
                                        arr[y] = temp;
                                }
                        }
                }
        }
        public static int halfSearch(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid;
                while (min <= max)
                {
                        mid = (min + max)/2;
                        if (key < arr[mid])
                        {
              
                                max = mid -1;
                        }
                        else if (key > arr[mid])
                        {
                                min = mid +1;
                        }
                        else{
                                return mid;
                        }
                }
                return -1;
        }
}

你的算法哪里有问题,具体的你看一下我给你修改后的代码吧!

评分

参与人数 1技术分 +1 收起 理由
房宝彬 + 1

查看全部评分

回复 使用道具 举报

class HalfSearch
{
        public static void arraySort(int[] arr)
        {
                for (int x = 0;x < arr.length-1 ; x++)
                {
                        for (int y = x+1;y < arr.length ;y++ )
                        {
                                if (arr[x] > arr[y])
                                {
                                        int temp = arr[x];
                                        arr[x] = arr[y];
                                        arr[y] = temp;
                                }
                        }
                }
        }
        public static int halfSearch(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid;
                while (min <= max)
                {
                        mid = (min + max)>>1;
                        if (key < arr[mid])
                        {
                                min = mid +1;//这里改成min =mid -1;当key值比中间值小的时候
                        }                          //那么key值介于min与mid之间,所以这时mid应该 - 1
                        else if (key > arr[mid])
                        {
                                max = mid -1; //这里改成max = mid +1;
                        }                           //当key比中间值大,那么key值在mid和max值中间
                        else                       //所以中间值应该+1
                                return min;
                }
                return -1;
        }
        public static void main(String[] args)
        {
                int[] array = {1,4,7,3,8,9,0,4,2};
                arraySort(array);
                int x = halfSearch(array,9);
                if (x != -1 )
                {
                        System.out.println("此值存在于排序后数组中的["+x+"]位置");
                }
                else
                        System.out.println("数组中不存在此数");
        }
}


评分

参与人数 1技术分 +1 收起 理由
房宝彬 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马