二分查找

二分查找

二分查找

二分查找

1.给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

力扣链接-704题-二分查找

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

思路：

二分查找，注意边界问题，使用左闭右开或者左闭右闭。 在while寻找中每次的边界处理都要根据区间的定义操作。

我习惯使用 左闭右闭 区间的思路。

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

2.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

力扣链接-35题-搜索插入位置

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

思路：

方法一：
直接遍历判断，变量index赋值为-1， 如果小于target，记录index，如果等于直接返回，如果大于target直接退出循环。

public int searchInsert(int[] nums, int target) {
    if (nums == null) {
        return -1;
    }
    int index = -1;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < target) {
            index = i;
        } else if (nums[i] == target) {
            return i;
        } else {
            break;
        }
    }
    return index == -1 ? 0 : index + 1;
}

方法二：
二分查找，采用左闭右闭区间。

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

3.在排序数组中查找元素的第一个和最后一个位置

leetcode-34题

public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) {
        return new int[]{-1, -1};
    }
    int left = 0;
    int right = nums.length - 1;
    int start = -1, end = -1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            if (left == right) {
                return new int[]{mid, mid};
            } else {
                for (int i = mid; i >= left; i--) {
                    if (nums[i] == target) {
                        start = i;
                    }
                }
                for (int i = mid; i <= right; i++) {
                    if (nums[i] == target) {
                        end = i;
                    }
                }
                return new int[]{start, end};
            }
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return new int[]{-1, -1};
}