黑马程序员技术交流社区

标题: 折半查找 [打印本页]

作者: 黑马连家华 时间: 2012-3-27 18:09
标题: 折半查找
/*
折半查找数组中是否有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("数组中不存在此数");
}
}

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

作者: 李哲 时间: 2012-3-27 18:31
将key < arr[mid]改为key > arr[mid]
key > arr[mid]改为key < arr[mid]

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

作者: 李见黎 时间: 2012-3-27 18:45

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;
      }
}

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

作者: 李见黎 时间: 2012-3-27 18:46

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;
      }
}

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

作者: 许飞翔 时间: 2012-3-27 18:49

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("数组中不存在此数");
      }
}

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

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