讨论/《二分查找》 - 二分查找/
《二分查找》 - 二分查找
共 28 个回复

没有说必须,主要看给的数据范围,本题给的数据规模比较小,两种写法都没问题。但当n > INT_MAX / 2 时,l + r 就可能溢出了,当然这也是因为下标非负,主要还是具体问题具体分析。

10

参考Java JDK 中 Arrays中的二分查找。

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

JS,好看

var search = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = (left + right)/2|0;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }

  }
  return -1;
};
4

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:38.9 MB, 在所有 Java 提交中击败了98.96%的用户

class Solution {
    public int search(int[] nums, int target) {
        return find(nums, 0, nums.length-1, target);
    }

    public int find(int[] nums, int low, int high, int target) {
        if (low <= high) {
            int mid = (high - low) / 2 + low;
            if (nums[mid] == target) {
                return mid;
            } 
            if (nums[mid] < target) {
                return find(nums, mid + 1, high, target);
            } 
            if (nums[mid] > target) {
                return find(nums, low, mid - 1, target);
            }
        }
        return -1;
    }
}
2

JavaScript版本~

var search = function (nums, target) {
    let left = 0, right = nums.length - 1
    while (left <= right) {
        let mid = Math.floor((left + right) / 2)    //向下取整防止奇数除不尽情况
        if(nums[mid] === target) {
            return mid
        }else if(target < nums[mid]) {
            right = mid - 1
        }else {
            left = mid + 1
        }
    }
    return -1
};
1

这是防止溢出的一个技巧

1

二分查找:
**1.左指针和右指针构成的区间问题:**是左开右闭,还是左闭右开?还是左闭右闭?

答案是都行,只要代码OK,看个人爱好。一个数组长度为10,数组下标是从0开始的,最后一个元素的下标是9。如果是左闭右开,l=0,r=len(nums),这样我们就完成了初始化。

**2.终止条件:**左闭右开区间不为空的话,r至少要大于等于l+1,也就是区间长度大于1的时候执行二分查找。

3.nums[m]和target的关系:

3.1。相等--直接返回,
3.2.大于--取左边的区间,r=m,而不是r=m-1,是因为r=m的位置是取不到,而r=m-1是有可能是答案
3.3.小于---取右边的区间,l=m+1,因为l的位置可以取到,而m已经不是答案了。

这里是将小于和等于的情况合并了,因为nums[m]有可能是答案。
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l+1<r: # 查找空间至少大于1m = (l+r)//2
            if nums[m] <= target:
                l = m
            else:
                r = m
        if nums[l] == target:
            return l
        else:
            return -1
1

python3

双指针法,关注三个点

  1. (双指针)初始值:left=0,right=len(nums)-1,mid=(left+right)//2
  2. (循环)终止条件:while循环的终止条件nums[left:right+1]=[],此时查找空间中无元素,证明数组nums中没有target【切片操作的终止值需为right+1,因为左闭右开,不+1则取不到right】
  3. (双指针)变化规则:如果target>nums[mid],left=mid+1;如果target<nums[mid],right=mid-1
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left=0
        right=len(nums)-1
        while(nums[left:right+1]!=[]):
            mid=(left+right)//2
            if target>nums[mid]:
                left=mid+1
            elif target<nums[mid]:
                right=mid-1
            else:
                return mid
        return -1
1

这里的 | 运算符取整有点骚~

c++

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