没有重复元素的时候

二分查找的2种写法

定义区间1: [left, right]

• while(left<=right)，要使用<=因为left=right是有意义的
• if(nums[mid]>target)right要赋值为mid-1，因为nums[mid]一定不是target

定义区间2: [left,right)

• while(left<right)，使用<因为left=right没意义，不包含right位置
• if(nums[mid]>target)right要赋值为mid，还是因为不包含right

代码演示

package algorithm.数组常见题.二分查找;

public class search {
    /**
     *
     * [704. 二分查找](https://leetcode.cn/problems/binary-search/description/)
     *  最基础款的二分查找，有序数组，没有重复元素
     */

    // 二分查找写法一：区间是[left, right]
    public static int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right) {
            int mid=left+((right-left)>>1);
            if(nums[mid]==target) return mid;
            if(nums[mid]>target) right=mid-1;
            if (nums[mid]<target) left=mid+1;
        }
        return -1;
    }

    // 二分查找写法二：区间是[left, right)
    public static int search2(int[] nums, int target) {
        int left=0;
        int right=nums.length; // 不同点1: 不包含right，所以是nums.length
        while(left<right) {  // 不同点2
            int mid=left+((right-left)>>1);
            if(nums[mid]==target) return mid;
            if(nums[mid]>target) right=mid; // 不同点3
            if(nums[mid]<target) left=mid+1;
        }
        return -1;
    }


    public static void main(String[] args) {
        int[] nums = {-1,0,3,5,9,12};
        System.out.println(search(nums, 2));
    }
}

递归的写法

package dataStructure.二分查找;

public class binarysearch {

    // 二分查找递归写法
    // 这里也是无重复元素
    public int binarySearch(int[] array, int low, int high, int target) {
        // 递归终止条件
        if (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] == target) return mid;
            if (array[mid] > target) return binarySearch(array, low, mid-1, target);
            if (array[mid] < target) return binarySearch(array, mid+1, high, target);
        }
        return -1;
    }

}

---

有重复元素的时候

package dataStructure.二分查找;

public class binarysearch2 {

    // 如果存在重复元素的时候，返回的索引【 可能是最左，可能是最右，可能在中间 】
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) right = mid - 1;
            if (nums[mid] < target) left = mid + 1;
            if (nums[mid] == target) return mid;
        }
        return -1;
    }

    // 如果是有重复元素，如果查找的元素重复，则找左侧第1个
    // 虽然我不知道找到的索引是在最左边还是中间还是最右边，但是我可以向左探测，走到最左边
    public static int search2(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                // 找到之后，往左找
                while (mid != 0 && nums[mid] == target) mid--;
                if (mid == 0 && nums[mid] == target) return mid;
                return mid + 1;
            }
        }
        return -1;
    }

    public int search3(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <=  right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        // 【如果target存在】返回的是target重复区间的最左侧索引
        //  【如果target不存在】返回第1个大于target的位置
        // 为什么呢？
        // 因为只要比target小，left就要往前进，最终会停在第一个大于等于target的位置
        // 只要大于等于target，right就要往前进，最终会停在最后一个小于target的位置
        return left;
        // 如果 return right;
        // 【如果target存在】返回的target重复区间左侧的前1个位置
        // 【如果target不存在】最终会停在最后一个小于target的位置
    }

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



}