黑马程序员——Java之二分查找算法

-------------------Java培训、Android培训、iOS培训、.Net培训、期待与您交流！ ---------------------

一、概念

二分查找算法也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。请注意这种算法是建立在有序数组基础上的。

二、算法思想

1、搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；2、如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。3、如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

三、优缺点

二分查找算法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，二分查找算法适用于不经常变动而查找频繁的有序列表。

四、实现思路

1、找出位于数组中间的值，并存放在一个变量中（为了下面的说明，变量暂时命名为temp）；2、需要找到的key和temp进行比较；3、如果key值大于temp，则把数组中间位置作为下一次计算的起点；重复1、2。4、如果key值小于temp，则把数组中间位置作为下一次计算的终点；重复1、2、3。5、如果key值等于temp，则返回数组下标，完成查找。

五、实现代码

public class BinarySearch {
      /**方式一：递归之二分查找；
      * @param dCount 获取递归的次数
      * @param xCount 获取循环的次数
      */
      private int dCount =0;
      private int xCount =0;
      public int getdCount(){
           return dCount ;
     }
      public int getxCount(){
           return xCount ;
     }
      /**
      * @param sortedArray 已排序的数组
      * @param start       开始位置
      * @param end         结束位置
      * @param findValue   要找的位置
      * @return             返回值所在数组的角标，找不到返回 - 1。
      */
      public int searchRecursive( int[] sortedArray, int start,int end,int findValue){
           dCount++;
           if (start<=end){
            int minddle=(start+end)>>1;//相当于(start+end)/2;
             int minddleValue=sortedArray[minddle];
             if (findValue==minddleValue)
               //如果查找的值与中间的值相同则直接返回中间值的角标。
                     return minddle;
             //如果查找的值小于中间的值则去前面部分查找。开始位置不变，结束位置为中间位置-1，再次递归。
             else if (findValue<minddle)
                  return searchRecursive(sortedArray,start,minddle-1,findValue);
             //如果查找的值大于中间的值则去后面部分查找。开始位置为中间值+1，结束位置不变，再次递归。
             else return searchRecursive(sortedArray,minddle+1,end,findValue);
          }
           else {
               return -1;//找不到值 返回-1；
          }
     }
      /**
      * 方式二：循环之二分查找；
      * @param sortedArray  已排序的数组
      * @param findValue    需要找的值
      * @param xCount       循环的次数
      * @return              循环查找值的角标，如果没有找到则返回 - 1;
      */
      public int sortedLoop( int[] sortedArray, int start,int end,int findValue){
           while (start<=end){
               xCount++;
               int minddle=(start+end)>>1;//相当于(start+end)/2;
              int minddleValue=sortedArray[minddle];
              if (findValue==minddleValue)
              return minddle;
              else if (findValue<minddleValue)
                     end=minddle-1;
              else    start =minddle+1;
                    }
           return -1;
     }
      public static void main(String[] args) {
           // TODO Auto-generated method stub
           int [] sortedArray={1,2,3,4,5,6,6,7,8,8,9,9,10,11};
           int findValue=1;
           int length=sortedArray.length ;
           int start=0;
           int end=length-1;
          BinarySearch bs= new BinarySearch();
           int pos1=bs.searchRecursive(sortedArray, start, end, findValue);
          System. err .println("要查找的" +findValue+ "的角标:"+pos1+ "递归次数:" +bs.dCount );
           int pos2=bs.sortedLoop(sortedArray, start, end, findValue);
          System. err .println("要查找的" +findValue+ "的角标:"+pos2+ "递归次数:" +bs.xCount );
     }
}