Go语言视频零基础入门到精通

javalearner

问题：
         如果一个数列已排序(从小到大)，查找指定元素在其中的位置。
      解法：
         利用数列已排序的特性，从数列的中间开始搜寻，如果这个数小于所搜寻的数，则该数左边的数
     一定都小于要搜寻的对象，所以无需浪费时间在左边的数；如果搜寻的数大于所搜寻的对象，则右边的
     数无需再搜寻，直接搜寻左边的数。如此类推，直到找到该元素，如果找不到则返回-1。
         例如从数列-4， -2， 4， 6， 9， 14， 23， 100中找14。
         1、首先从中间(0 + 7)/2=4开始:
         < -4 -2 4 6 9 14 23 100 >
         2、由于9小于23，所以搜寻右边的数列
         -4 -2 4 6 9 < 14 23 100 >
         3、由于23大于14，所以搜寻左边的数列
         -4 -2 4 6 9 < 14 > 23 100
         4、找到目标，返回位置5。
      核心代码：
     1、 迭代实现  
      
      
         
      //
      迭代实现
      

         
      static
      
      int
       search(
      int
      [] numbers,
      int
       num) {
     
      int
       low
      =
      
      0
      , high
      =
       numbers.length
      -
      
      1
      ;
     
      int
       mid;
     
      while
       (low
      <
       high) {
             mid
      =
       (low
      +
       high)
      /
      
      2
      ;
         
      if
       (numbers[mid]
      ==
       num)   
      //
      找到则返回
      

              
      return
       mid;

         
      if
       (numbers[mid]
      >
       num)   
      //
      大于目标，找左边
      

              high
      =
       mid
      -
      
      1
      ;
         
      else
                  
      //
      小于目标，找右边
      

              low
      =
       mid
      +
      
      1
      ;
     }
     
         
      return
      
      -
      1
      ;            
      //
      找不到，返回-1
      

          }
      
     2、 递归实现  
      
      
         
      static
      
      int
       search(
      int
      [] numbers,
      int
       num,
      int
       low,
      int
       high) {
         
     
      //
      下边界大于上边界，没必要进行下去了
      

         
      if
      (low
      >
       high)
         
      return
      
      -
      1
      ;
         
     
      //
      中间值
      

         
      int
       mid
      =
       (low
      +
       high)
      /
      
      2
      ;        
     
      if
       (numbers[mid]
      ==
       num)   
      //
      找到则返回
      

              
      return
       mid;

     
      if
       (numbers[mid]
      >
       num)        
      //
      大于目标，找左边
      

              
      return
       search(numbers, num, low, mid
      -
      
      1
      );
     
      else
                     
      //
      小于目标，找右边
      

              
      return
       search(numbers, num, mid
      +
      
      1
      , high);
     }
      
     全部代码：  
     
      
      
      Code
      

        package com.icescut.classic.algorithm;

public class BinarySearch {

     public static void main(String[] args) {
         int[] numbers = { -4, -2, 4, 6, 9, 14, 23, 100 }; // 已排序
         
         //递归实现
         int res = search(numbers, 14,0,numbers.length);
         System.out.println("position in " + res);
         
         //迭代实现
         res = search(numbers, 14);
         System.out.println("position in " + res);

     }

     //递归实现
     static int search(int[] numbers, int num, int low, int high) {
         
         //下边界大于上边界，没必要进行下去了
         if(low > high)
             return -1;
         
         //中间值
         int mid = (low + high) / 2;        
         if (numbers[mid] == num)        //找到则返回
             return mid;

         if (numbers[mid] > num)            //大于目标，找左边
             return search(numbers, num, low, mid - 1);
         else                    //小于目标，找右边
             return search(numbers, num, mid + 1, high);
     }

     //迭代实现
     static int search(int[] numbers, int num) {
         int low = 0, high = numbers.length - 1;
         int mid;
         while (low < high) {
             mid = (low + high) / 2;
             if (numbers[mid] == num)    //找到则返回
                 return mid;

             if (numbers[mid] > num)        //大于目标，找左边
                 high = mid - 1;
             else                //小于目标，找右边
                 low = mid + 1;
         }
         return -1;                //找不到，返回-1
     }
}

      
     说明：
         迭代实现与递归实现的思想都是一样的，所是最好使用迭代以减少开销。
  
     
   
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/14/000828656.zip