LeetCode｜【704 二分查找】

704.二分查找

二分查找

使用二分法的前提条件：
1.数组为有序数组
2.数组中无重复元素

区间的定义有两种写法：左闭右闭 [left,right] 和 左闭右开 [left,right)，由此二分法也有两种写法：

1.target在 [left,right] 区间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
            int mid = (left + right) / 2;
            if(target < nums[mid])
                right = mid - 1;
            else if(target > nums[mid])
                left = mid + 1;
            else
                return mid;
        }
    return -1;
    }
};

2.target在 [left,right) 区间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right){
            int mid = (left + right) / 2;
            if (target < nums[mid])
                right = mid;
            else if (target > nums[mid])
                left = mid + 1;
            else
                return mid;
        }
    return -1;
    }
};

【 为防止python忘得太快，附上python 】

1.target在 [left,right] 区间

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if target < nums[mid]:
                right = mid - 1
            elif target > nums[mid]:
                left = mid + 1
            else:
                return mid
        return -1

2.target在 [left,right) 区间

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            mid = (left + right) // 2
            if target < nums[mid]:
                right = mid
            elif target > nums[mid]:
                left = mid + 1
            else:
                return mid
        return -1