黑马程序员技术交流社区

标题: 折半方法怎么应用？ [打印本页]
作者: 李会启    时间: 2012-2-22 16:12
标题: 折半方法怎么应用？
在一个有序数组中怎么用折半法怎么插入一个数并且保证数组的有序性，同时获取该数的插入数组后的位置。
作者: 胡威    时间: 2012-2-22 16:25
毕老师视频第4天07，和第17天12中都有讲解到
假设有序数组的最小脚标和最大脚标为min和max
int mid=(max+min)/2;得到一个中间位置的脚标，然后看这个角标上的元素和我们想插入的这个元素的大小关系，如果要插入的元素大，就把mid+1赋给min,然后在新的min到max的范围内继续mid=(max+min)/2，然后在比较这个mid脚标的元素和要插入的元素的大小，以此类推；如果要插入的元素小，就把mid-1赋给max,然后再在新的min到max的范围内继续mid=(max+min)/2，以此类推。
如果要插入的这个数在数组中本来就存在，那么返回的数组中的这个元素的角标+1或者-1都可以作为该插入元素的脚标。
如果要插入这个数在数组中不存在，则跳出循环，最后的min值就是要插入的元素应该在数组中的脚标。
作者: 刘基军    时间: 2012-2-22 17:47
供参考:
  1. int [] a = {2,4,6,8,14,24,34,50,90};
  2.                 int num = 5;
  3.                 int max = a.length-1;
  4.                 int min = 0;
  5.                 int mid = (max+min)/2;
  6.                 int temp =0;
  7.                
  8.                 while(true)
  9.                 {
  10.                         if(min>=max)
  11.                         {
  12.                                 temp = mid;
  13.                                 break;
  14.                         }
  15.        
  16.                         mid = (max+min)/2;       
  17.                                        
  18.                         if(num<a[mid])
  19.                         {
  20.                                 max =        mid-1;
  21.                         }
  22.                         else if(num>a[mid])
  23.                         {
  24.                                 min = mid+1;       
  25.                         }
  26.                         else
  27.                         {
  28.                                 temp = mid+1;//遇到相同，则插入在其后面
  29.                                 break;
  30.                         }

  32.                 }
  33.                
  34.                 for(int i:a)
  35.                 {
  36.                         System.out.print(i+" ");
  37.                 }
  38.                 System.out.println();
  39.                 System.out.println(temp);//得到插入位置
  40.        
  41.                 int [] b = new int[10];
  42.                 for(int i=0;i<b.length;i++)
  43.                 {
  44.                         if(i<temp)
  45.                         {
  46.                                 b[i] = a[i];
  47.                         }
  48.                         else if(i==temp)
  49.                         {
  50.                                 b[i] = num;
  51.                         }
  52.                         else
  53.                         {
  54.                                 b[i] = a[i-1];       
  55.                         }
  56.                         System.out.print(b[i]+" ");
  57.                 }
复制代码
作者: dangfei    时间: 2012-2-22 17:54
public static void main(String[] args) {
                // TODO Auto-generated method stub
        int[] a={3,5,8,9,10,15,17};
        new Test3().find(a, 0, a.length, 15);
        }
        void find(int[] a,int start,int end,int digit)
        {
                int mid=(start+end)/2;
                if (start==mid)
                {
                        //在其后插入digit
                        System.out.println("插入如位置是："+(start+1));
                        return;
                }
                if(digit>a[mid])
                        find(a, mid, end, digit);
                else if(digit<a[mid])
                        find(a, start, mid, digit);
                else if (digit==a[mid]) {
                        //在其后插入digit
                        System.out.println("插入如位置是："+(mid+1));
                        return;
                }
        }
作者: 陈伟    时间: 2012-2-22 20:25
public class Search {

public static boolean binarySearch(int[] a,int x,int left,int right){//二分查找的主方法
  if(x==a[left]||x==a[right])return true;     //找到，返回真
  if(right-left<2)return false;               //可找元素小于3,由上一步说明没有，返回假
  int mid = (left+right)/2;                   //否则：二分  
  if(x==a[mid])return true;                   //中间元素OK，返回OK
  else{                                       //否则
   if(x>a[mid])return binarySearch(a,x,mid+1,right);//大于中间元素找右半部分
   else return binarySearch(a,x,left,mid-1);        //小于中间元素找左半部分
  }
}

public static final int[] sort(int[] a){     //int数组 的 排序方法
  for (int i = 0; i < a.length; i++) {
   for (int j = 0; j < a.length; j++) {
    if(a[i]<a[j]){
     swap(a,i,j);
    }
   }
   
  }
  return a;
}

private static void swap(int[] a, int i, int j) { //数组元素交换子函数
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

public static void print(int[] a){              //打印函数
  System.out.println();
  for (int i = 0; i < a.length; i++) {
   System.out.print(a[i]);
   if(i!=a.length-1)System.out.print(",");
  }
  System.out.println();
}

public static void main(String[] args) {        //测试方法
  int[] a = {90, 12, 21, 32, 51, 78, 87, 98};
  print(sort(a));
  System.out.println(binarySearch(sort(a), 40, 0, a.length-1));
}
}



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