二分查找思想及实现

使用二分查找必须满足集合有序，只有集合有序时才能使用二分

思想：找出中点元素，此时左侧全是小于它的元素，右侧全是大于它的元素，根据需要选择左半边或右半边，直到找到对应元素

实现：

// 递归实现
public boolean find(int[] num, int start, int end, int val) {
    if (start > end) {
        return false;
    }
    int mid = start + (end - start) / 2;
    if (num[mid] == val) {
        return true;
    }
    return num[mid] > val ? find(num, start, mid - 1, val) : find(num, mid + 1, end, val);
}

// 非递归实现
public boolean find2(int[] num, int start, int end, int val) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (num[mid] == val) {
            return true;
        } else if (num[mid] > val) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return false;
}