当前位置：首页 > article >正文

算法与数据结构--二分查找

article 2024/10/8 2:51:23

原理

二分查找动图

简单说就是每次二分取中间值，然后将中间值与我们要找的值比较，如果比它大就移动左边界到其右侧，如果比它小就移动右边界到其左侧。直到中间值等于该值或者经过移动直至右边界在左边界左侧为止。

二.具体实现

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int mid = 0;
    System.out.println(left + " " + right);

    while (left <= right) {
        mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
//            right left
//            right=mid left right小于target ，target应该在right的右边,target=right+1
//            right left=mid left大于target,target应该在left的坐标，target=left
//            if (mid == left) {
//                return left;
//            } else {
//                return right+1;
//            }
    return right + 1; // 应该插入的位置
}