【LeetCode 704】二分查找

🎯 请点击上方原题链接，查看题目描述👆

💭 解题思路#

二分查找题，要区分有效的区间，两种情况 [) 和[]

💻 代码实现#

左闭右开的情况：#

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length;
        //防止溢出写法
        int mid = left + (right - left) / 2;

        while(left < right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }

            if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}

左闭右闭的情况#

class Solution {
    public int search(int[] nums, int target) {
        //这里right = nums.length - 1 是有效范围，所以是闭合区间
        int left = 0,right = nums.length - 1;

        int mid = left + (right - left) / 2;
        //如果有效就应该 <= 这样不会漏掉
        while(left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }

            //这里是有效区间，所以mid不用考虑了，需要考虑 mid 前面的元素
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}