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) >> 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) {
            int mid = (start + end) >> 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);
        int i1 = nonRecursionBinarySearch(nums, 1);
        System.out.println(i1);
    }

}
@@ -683,33 +683,32 @@
   int mid = 
-(
 start + 
 end) %3E%3E 1;%0D%0A
@@ -687,36 +687,45 @@
 t mid = start + 
+(
 end)
+ - start
  %3E%3E 1;%0D%0A        
@@ -1329,32 +1329,127 @@
 tart %3C= end) %7B%0D%0A
+            //%E9%98%B2%E6%AD%A2(start+end)%3E%3E1%E6%BA%A2%E5%87%BA%0D%0A            //JDK%E4%B8%AD%E7%9A%84Arrays.binarySearch%E4%BD%BF%E7%94%A8(low + high) %3E%3E%3E 1;%0D%0A
             int 
@@ -1458,17 +1458,16 @@
 d = 
-(
 start + 
 end)
@@ -1462,19 +1462,28 @@
 start + 
+(
 end
+ - start
 ) %3E%3E 1;%0D
@@ -1960,13 +1960,8 @@
    i
-nt i1
  = n
@@ -2023,17 +2023,16 @@
 rintln(i
-1
 );%0D%0A    

fix binary search