二分查找算法java版实现(递归实现与非递归实现)

二分查找，如果一个有序集合，需要查找其他特定 的查询，我们可以使用二分查找，加快查询速度，具体的思路就是，每次取有序数组的中间元素与待查找元素进行比较，从而缩小一半的查询范围。

java版本非递归方式实现二分查找：

      /**
       *
       * @param source
       * @param search
       * @return 返回匹配的下标
       */
     	public static final int twoPointSearch(int[] source, int search) {
     		int min = 0;
     		int max = source.length - 1;
     		int mid = ( max - min  ) >> 1 ;
     		while (mid >= 0 && mid <= max && max >= min) {
     			if(source[mid] == search ) {
      return mid;
      			}
     			if(source[mid] > search ) { // 在souce前半部分查找
       max = mid - 1;
      			} else { // 在souce后半部分查找
       min = mid + 1;
      			}
      			mid = ((max-min) >> 1) + min ;
      		}
     		return -1;
      	}
  
 

      /**
       * 二分查找，递归版本
       * @param source 有序数组
       * @param search 待查询元素
       * @param min 开始下标
       * @param max 结束下标（初始值为有序数组长度减1）
       * @return
       */
     	public static final int twoPointSearchByRecursion(int[] source, int search, int min, int max) {
     		int mid = ((max-min) >> 1) + min ;
     		if(mid >= 0 && mid <= max && max >= min ) {
     			if(source[mid] == search ) {
      return mid; //返回下标
      			}
     			if(source[mid] > search ) { // 在souce前半部分查找
       max = mid - 1;
      			} else { // 在souce后半部分查找
       min = mid + 1;
      			}
     			return twoPointSearchByRecursion(source, search, min, max) ;
      		} //否则结束递归
     		return -1;
      	}
  
 

      /**
       * 二分查找
       */
     	public static final void testTwoPointSearch() {
     		int[] source = new int[] { 1,13,21,35,39,51,62,78,99 };
      		System.out.println(twoPointSearch(source, 22));
      		System.out.println(twoPointSearch(source, 21));
      		System.out.println(twoPointSearch(source, 1));
      		System.out.println(twoPointSearch(source, 99));
      		System.out.println(twoPointSearchByRecursion(source, 22, 0, source.length-1));
      		System.out.println(twoPointSearchByRecursion(source, 21, 0, source.length-1));
      		System.out.println(twoPointSearchByRecursion(source, 1, 0, source.length-1));
      		System.out.println(twoPointSearchByRecursion(source, 99, 0, source.length-1));
      	}
  
 

文章来源: blog.csdn.net，作者：中间件兴趣圈，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/prestigeding/article/details/72818506