leetcode35 插入的位置

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

你可以假设数组中无重复元素。

思路：二分查找

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public int searchInsert(int[] nums, int target) {
     
    
   

    

     

    
    

     
 int len = nums.length;
     
    
   

    

     

    
    

     
 if (nums[len - 1] < target) {
     
    
   

    

     

    
    

     
 return len;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 int left = 0;
     
    
   

    

     

    
    

     
 int right = len - 1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while (left <= right) {
     
    
   

    

     

    
    

     
 int mid = (left + right) / 2;
     
    
   

    

     

    
    

     
 // 等于的情况最简单，我们应该放在第 1 个分支进行判断
     
    
   

    

     

    
    

     
 if (nums[mid] == target) {
     
    
   

    

     

    
    

     
 return mid;
     
    
   

    

     

    
    

     

       } else if (nums[mid] < target) {
     
    
   

    

     

    
    

     
 // 题目要我们返回大于或者等于目标值的第 1 个数的索引
     
    
   

    

     

    
    

     
 // 此时 mid 一定不是所求的左边界，
     
    
   

    

     

    
    

     
 // 此时左边界更新为 mid + 1
     
    
   

    

     

    
    

     

       left = mid + 1;
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     
 // 既然不会等于，此时 nums[mid] > target
     
    
   

    

     

    
    

     
 // mid 也一定不是所求的右边界
     
    
   

    

     

    
    

     
 // 此时右边界更新为 mid - 1
     
    
   

    

     

    
    

     

       right = mid - 1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 // 注意：一定得返回左边界 left，
     
    
   

    

     

    
    

     
 // 如果返回右边界 right 提交代码不会通过
     
    
   

    

     

    
    

     
 // 【注意】下面我尝试说明一下理由，如果你不太理解下面我说的，那是我表达的问题
     
    
   

    

     

    
    

     
 // 但我建议你不要纠结这个问题，因为我将要介绍的二分查找法模板，可以避免对返回 left 和 right 的讨论
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 // 理由是对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
     
    
   

    

     

    
    

     
 // 在上面的 while (left <= right) 退出循环以后，right < left，right = 0 ，left = 1
     
    
   

    

     

    
    

     
 // 根据题意应该返回 left，
     
    
   

    

     

    
    

     
 // 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return left;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103340240