二分查找算法是一种在有序数组中查找特定元素的搜索算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一部分确定该部分没有要查找的元素，那么就可以不再对这部分进行搜索，逐渐缩小搜索范围。

1、简单版本的二分查找 {#title-1}

因为low和high的更新,必须在循环体内部处理,所以如果目标不存在则会出现死循环

public int binarySearch(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while(low <= high) {
        int mid = low + (high - low) / 2;
        if(nums[mid] == target) {
            return mid;
        }
        if(nums[mid] < target) {
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }
    return -1;
}

2、改进版本的二分查找 {#title-2}

对于上述可能出现死循环的问题，可以在循环条件的更新部分进行修改。具体来说，当目标值大于中间元素时，low需要变成mid+1；当目标值小于中间元素时，high需要变成mid而不是mid-1。

public int binarySearch(int[] nums, int target) {
    int low = 0, high = nums.length;
    while(low < high) {
        int mid = low + (high - low) / 2;
        if(nums[mid] == target) {
            return mid;
        }
        if(nums[mid] < target) {
            low = mid + 1;
        }else{
            high = mid;
        }
    }
    return -1;
}

3、递归版本的二分查找 {#title-3}

除了非递归外，二分查找还可以使用递归来实现。这种方法的关键在于数组的查找范围在每次递归调用时都会变小。

public int binarySearch(int[] nums, int target) {
    return binarySearch(nums, target, 0, nums.length - 1);
}

private int binarySearch(int[] nums, int target, int low, int high) {
    if(low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if(nums[mid] == target) {
        return mid;
    }
    if(nums[mid] < target) {
        return binarySearch(nums, target, mid + 1, high);
    }else{
        return binarySearch(nums, target, low, mid - 1);
    }
}