前言

之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两天晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀

数组的文章合集

• 六六力扣刷题数组之理论基础

首先我们来看看 二分法的主流套路

二分法的写法共分两种分别是：1.定义target在左闭右闭区间 2.定义target在左闭右开区间。 方法1. 定义target在左闭右闭区间，即[left, right] 1.while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。 2.if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle – 1。

方法2. 定义target在左闭右开区间，即[left, right) 1.while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的。 2.if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]。

反正大家记住 如果是左闭右闭，那么我们就是 middle - 1， 如果是左闭右开 我们就是mmiddle

思想

二分查找是计算机科学中最基本、最有用的算法之一。 它描述了在有序集合中搜索特定值的过程。

二分查找中使用的术语： 目标 Target —— 你要查找的值 索引 Index —— 你要查找的当前位置 左、右指示符 Left，Right —— 我们用来维持查找空间的指标 中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引

搜索插入位置

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

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

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

题解

要在数组中插入目标值总共有四种情况：

1.目标值在数组所有元素之前

2.目标值等于数组中某一个元素

3.目标值插入数组中的位置

4.目标值在数组所有元素之后

package com.six.finger.leetcode.nine;
public class searchInsert {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) {
            return target;
        }
        int right = nums.length-1;
        int left = 0;
        while (left <= right) {
            int mid =left+ (right - left) / 2;
            if (target > nums[mid]) {
                left = mid+1;
            } else if (target < nums[mid]){
                right = mid-1;
            }else {
                return mid;
            }
        }
        return right+1;
    }
}

结束

今天我们就到这了，很简单的一个题，大家多思考下，下次肯定就不会乱了，不然每次写二分，都是感觉会写，但是最终都写不对，我是小六六，三天打鱼，两天晒网！