再探二分查找

之前在code_33里对二分查找有了一点理解，当时理解的点在于while循环中的if涉及的区间问题，简简单单理解为>,<,=的三个if并集为全集就行了，现在看来想法未免有点幼稚。

三种问题

不妨假设一个数组 nums = [1, 2, 3, 3, 3, 4], target = 3

寻找target

寻找第一个target

寻找最后一个target

问题一

写法一

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

写法二

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

两种写法的区别

1. 初始化left，right不同

2. while的判断不同

先明确一点，left,right的初始化值表示了搜索区间
写法一表示的搜索区间为[left, right],写法二的搜索区间为[left, right),正是由于搜索区间的不同导致了while判断时候的不同，因为方法一退出while的条件是left = right + 1, 方法二的退出条件是left = right,

while退出时方法一的搜索区间可表示为[right + 1, right] while退出时方法二的搜索区间可表示为[right, right)

此时两个搜索区间都为空，表示所有元素已经被搜索，因此两种写法都可以

问题二

写法一

public static int leftBinarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 退出时left = right + 1, 
        // 因此left范围为[0, nums.length]
        // 同理right范围为[-1, nums.length-1]
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                //相等时右侧向左逼近,left停止在target，right停在target前一个
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                //小于的话left还要再加1,因此left停止在target
                left = mid + 1;
            }
        }
        //nums[left] != target 表示在left停在数组中间没找到
        //left >= nums.length 表示整个数组都小于target
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

问题三

写法一

public static int rightBinarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 退出时left = right + 1,
        // 因此left范围为[0, nums.length]
        // 同理right范围为[-1, nums.length-1]
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                //相等时右侧向右逼近,left停止在target后一个，right停在target
                left = mid + 1;
            } else if (nums[mid] > target) {
                //小于的话right还要再减1,因此right停在target
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        //nums[left] != target 表示在right停在数组中间没找到
        //right < 0表示整个数组都大于target
        if (right < 0 || nums[left] != target) {
            return -1;
        }
        return right;
    }