[数据结构与算法]LeetCode——1.数组1：二分查找（35.搜索插入位置）

?

目录

数组

二分查找

方法

35.搜索插入位置

?

数组

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标下对应的数据。

注意

• 数组下标是从0开始的
• 数组的地址是连续的
• 在删除或者增加数组元素时，数组元素不能删除只能覆盖，所以要移动元素

二分查找

使用条件

1. 数组元素要有序的
2. 有的题也会出现有重复元素的情况

二分法的边界问题比较重要，关于区间的定义一般有两种，一种是左闭右闭[left,right]，第二种左闭右开[left,right)，这就涉及到循环条件和right值的处理不同

mid防止溢出：

左闭右闭[left,right]：int mid = left + ((right - left) / 2);

左闭右开[left,right)：int mid = left + ((right - left) >> 1);

方法

以LeetCode?704.二分查找为例

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

1.左闭右闭[left,right]

target在[left,right]区间内，所以left=right是有意义的，所以，循环条件和right值的处理：

• while (left <= right)?
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target（因为右面是闭区间，所以target和left比较过了），那么接下来要查找的左区间结束下标位置就是 middle - 1

例：查找元素1

704.二分查找的Java代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) / 2); //为了防止溢出，和（left+right）/2一样
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] > target) {
                right = mid - 1;
            }else if(nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }
}

2.左闭右开[left,right)

target在[left,right)区间内，所以left=right没有意义的，所以，循环条件和right值的处理：

• while (left <right)?
• right要指向nums.length
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle] （因为右区间是开的，所以如果right更新为middle-1，就比较不到当前的right值了。在左区间进行寻找）

例：查找1元素

704.二分查找的Java代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1); //为了防止溢出
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] > target) {
                right = mid;
            }else if(nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }
}

35.搜索插入位置

题目链接

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

上面的母题会了之后，这道题就很简单了，思路基本一样，唯一的不同就是当目标值不存在时函数的返回值。这里也可以讨论两种区间的情况。

1.左闭右闭[left,right]

前面的思路一样，现在来还原最差的情况（最后一次循环）：目标值不存在。例：查找元素2

模拟最后一次left=right的循环，mid指向的值小于目标值2，所以left会更新为mid+1，此时的值就是目标值应该在的位置，让函数值返回left。找目标值7的时候同理。

Java代码

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

2.左闭右开[left,right)

还原最差的情况（最后一次循环）：目标值不存在，例：查找元素7?

此时是最后一次循环的情况，mid指向的值小于目标值，所以left会向右移一位，所以，函数的返回值是left/right均可。

Java代码

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

?

?

?

?

?

?