package cn.codepub.algorithms.strings;

/**
 * <p>
 * Created with IntelliJ IDEA. 2015/10/15 17:15
 * </p>
 * <p>
 * ClassName:BinarySearch
 * </p>
 * <p>
 * Description:二分查找
 * 注意点：数组在传递进来之前一定是排好序的数组，采用递归实现的方法一定要提供出口
 * </P>
 *
 * @author Wang Xu
 * @version V1.0.0
 * @since V1.0.0
 */
public class BinarySearch {

    /**
     * 递归方式实现二分查找
     *
     * @param nums  查找的数组
     * @param start 开始下标
     * @param end   结束下标
     * @param key   查找元素
     * @return 查找元素的下标，当未查到的时候，返回-1
     */
    private static int recursionBinarySearch(int[] nums, int start, int end, int key) {
        if (start > end) {
            return -1;
        }
        int mid = start + (end) - start >> 1;
        if (nums[mid] == key) {
            return mid;
        } else if (nums[mid] > key) {
            //说明key在当前分组的左半边
            return recursionBinarySearch(nums, start, mid - 1, key);
        } else {
            //在右半边
            return recursionBinarySearch(nums, mid + 1, end, key);
        }


    }

    /**
     * 非递归方式实现二分查找
     *
     * @param nums 查找的数组
     * @param key  查找元素
     * @return 查找元素的下标，当未查到返回-1
     */
    private static int nonRecursionBinarySearch(int[] nums, int key) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            //防止(start+end)>>1溢出
            //JDK中的Arrays.binarySearch使用(low + high) >>> 1;
            int mid = start + (end - start) >> 1;
            if (nums[mid] == key) {
                return mid;
            } else if (nums[mid] > key) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 11};
        int i = recursionBinarySearch(nums, 0, nums.length - 1, 11);
        System.out.println(i);
        i = nonRecursionBinarySearch(nums, 1);
        System.out.println(i);
    }

}
@@ -699,21 +699,21 @@
 t + 
+(
 (end
-)
  - start
  %3E%3E 
@@ -708,21 +708,23 @@
  - start
+)
  %3E%3E 1
+)
 ;%0D%0A     
@@ -1365,16 +1365,20 @@
 tart
-+
+ + 
 end)
+ 
 %3E%3E1
+ 
 %E6%BA%A2%E5%87%BA%0D%0A
@@ -1468,16 +1468,17 @@
 start + 
+(
 (end - s
@@ -1483,24 +1483,25 @@
  start) %3E%3E 1
+)
 ;%0D%0A         
@@ -1951,24 +1951,588 @@
 rintln(i);%0D%0A
+        i = recursionBinarySearch(nums, 0, nums.length - 1, 12);%0D%0A        System.out.println(i);%0D%0A        i = recursionBinarySearch(nums, 0, nums.length - 1, 0);%0D%0A        System.out.println(i);%0D%0A        i = nonRecursionBinarySearch(nums, 11);%0D%0A        System.out.println(i);%0D%0A        i = nonRecursionBinarySearch(nums, 12);%0D%0A        System.out.println(i);%0D%0A        i = nonRecursionBinarySearch(nums, 0);%0D%0A        System.out.println(i);%0D%0A        nums = new int%5B%5D%7B1%7D;%0D%0A        i = recursionBinarySearch(nums, 0, nums.length - 1, 1);%0D%0A        System.out.println(i);%0D%0A
         i = 
@@ -2599,18 +2599,16 @@
 ln(i);%0D%0A
+
     %7D%0D%0A
-%0D%0A
 %7D

fix binary search