二分法（折半）查找【Java】

二分法（折半）查找【Java】

1. 适用条件： 有序、无重复元素
2. 二分法查找效率要高于“一个挨着一个”的这种查找方式。

二分法查找原理：

arr数组：10(0下标) 23 56 89 100 111 222 235 500 600(下标9) 		
目标：找出600的下标

(0 + 9) / 2 --> 4（中间元素的下标）		
arr[4]这个元素就是中间元素：arr[4]是 100
判断100 < 600，说明被查找的元素在100的右边。
那么此时开始下标变成：4 + 1

(5 + 9) / 2 --> 7（中间元素的下标）
arr[7] 对应的是：235
判断235 < 600，说明被查找的元素在235的右边。
开始下标又进行了转变：7 + 1
			
(8 + 9) / 2 --> 8（中间元素的下标）
arr[8] --> 500
判断500 < 600，说明被查找的元素在500的右边。
开始元素的下标又发生了变化：8 + 1

(9 + 9) / 2 --> 9（中间元素的下标）
arr[9]是600，正好和600相等，此时找到了。

代码实现

第一种：定义target在一个左闭右闭的区间[left ,right]

• ①while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• ②if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

public class binarySearch {
    public static void main(String[] args) {
        int[] array = {5, 9, 15, 36, 84, 96, 125, 456, 535};
        System.out.println(binary_Search(array, 535));
    }
    private static int binary_Search(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

---

• 第二种：定义 target 是在一个左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

• ①while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的

• ②if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

private static int binary_Search_2(int[] array, int target) {
    int left = 0;
    int right = array.length;
    while (left < right) {
        int mid = left+((right-left)/2);
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

例题：
leetCode35搜索插入位置
leetCode34在排序数组中查找元素的第一个和最后一个位置
leetCode69 X的平方根
leetCode367 有效的完全平方数