二分排序和二分查找

二分法排序以及二分法查找

二分法原理：
在插入第i个元素时，对前面的0-i-1个元素进行折半，先跟他们中间的元素进行比较
如果比中间元素大则对前面在进行折半，大则对后半部分进行折半。直到左边大于右边
然后把第i个元素前一位与目标位置之间的所有元素后移，再把第i个元素放在目标位置。
下面将二分法用代码实现一下

public  void barnarySort(int arr[]){
    for(int i=0;i<arr.length;i++){
         int min=0;
         int end=i-1;
         int start=0;
         int tmp=arr[i];
         while(start<=end){
             min=(start+end)/2;
             if(arr[min]>tmp){
                 end=min-1;
             }else{
                 start=min+1;
             }            
         }
     for(int j=i-1;j>end;j--){
        data[j+1]=data[j];
     }
        data[end+1]=tmp;
    }
}

二分法查找原理：
使用二分法查找的方法是数组必须是排好序的，查找数x时先从中间查找，如果x小于中间数则在对前前半部分折半查找负责对后半部分进行折半查找，如此直到找到x元素，或者查找不到返回-1；
请看实现的代码

  public int getIndex(int arr[],int x){
    
         int start=0;
         int end=arr.length-1;
         int min=0;
         while(start<=end){
              min=(strat+end)/2;
              if(x==arr[min]){
                return min;
              } esle if(x<arr[min]){
                end=min-1;
              }else if(x>arr[min){
                 start=min+1;
              }
         }
       return -1;
      
}

具体的实现方法就是上面；