526互联

L-3: 35.搜索插入位置

发布时间 2023-11-05 20:10:21作者: 翻斗花园小美Q

首先解释一下二分查找的时间复杂度为logn的问题：

　　假设长度为 n，简单理解如下：

　　第1次查找是 n/2 = n/21

　　第2次查找是 n/4 = n/22

　　第3次查找是 n/8 = n/23

　　第4次查找是 n/16 = n/24

　　..... 最后二分查找查到结果集只有一个，表示定位到了该数据

　　第 x 次查找是 n/2x = 1

　　推到出 2x = n，x = log2n

class Solution {
    public int searchInsert(int[] nums, int target) {
        // Map <Integer, Integer> map = new HashMap<>();
        // for (int i = 0; i < nums.length; i++) {
        //     map.put(nums[i], i);
        // }
        // if (map.containsKey(target)) {
        //     return map.get(target);
        // }else {
        //     return -1;
        // }

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

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

    }
}

关键点：当不满足while循环的时候直接返回left的值，就是我们要找的下标

（我也不知道为什么写了一段map的代码）