1 package com.gxf.search; 2  3 /** 4  * 测试折半查找or二分查找 5  * @author xiangfei 6  * 7  */ 8 public class BiSearch { 9     10     /**11      * 非递归实现,从第1个元素开始查找12      * @param array13      * @param k14      * @return 0 查找失败15      */16     public int biSearch(int array[], int k){17         int low = 1;18         int high = array.length - 1;19         20         while(low <= high){21             int mid = (low + high) / 2;22             if(k == array[mid]){23                 return mid;24             }25             if(k > array[mid]){26                 low = mid + 1;                27             }28             else{29                 high = mid - 1;30             }31         }32         return 0;33     }34     35     /**36      * 递归实现37      * @param array38      * @param k39      * @param l40      * @param h41      * @return42      */43     public int biSearch(int array[], int k, int l, int h){44         if(l > h){45             return 0 ;46         }47         if(k == array[(l + h) / 2])48             return (l + h) / 2;49         else if(k > array[(l + h) / 2]){50             return biSearch(array, k, (l + h) / 2 + 1, h);51         }52         else{53             return biSearch(array, k, l, (l + h) / 2 - 1);54         }55     }56 57     public static void main(String[] args) {58         BiSearch biSearch = new BiSearch();59         int array[] = {0,1,3,4,5,6,7};60         System.out.println(biSearch.biSearch(array, 5));61         System.out.println(biSearch.biSearch(array, 5, 1, array.length - 1));62 63     }64 65 }