vlambda博客
学习文章列表

算法专栏

算法专栏，每日推送。算法是程序员内功，分享算法知识、文章、工具、算法题、教程等

0篇原创内容

Official Account

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

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

示例1:

输入: [1,3,5,6], 5

   
     
     
   

    
      
      
    输出: 
    
      
      
    2
   
     
     
   
示例2:
输入: [1,3,5,6], 2
输出: 1
  
    
    
  

   
     
     
   思路分析
  
    
    
  
  
    
    
  

   
     
     
   二分查找法在每次查找之后，会将查找区间缩小一半。要写出正确的二分查找法，需要明确：
  
    
    
  
  
    
    
  

   
     
     
   一是查找区间的定义。左闭右闭区间[left,right]表示区间内的所有元素都要考察；左闭右开区间[left,right)表示right所指的元素不在考察范围内。
  
    
    
  
  
    
    
  

   
     
     
   不同的定义方式，循环结束的条件是不一样的。
   
     
     
   对于左闭右闭区间[left,right]来说，循环结束的条件是left>right；对于左闭右开区间[left,right)来说，循环结束的条件是left==right。
  
    
    
  
  
    
    
  

   
     
     
   二是新一轮搜索的区间。新一轮的搜索区间是由上一步区间的定义来决定的。
  
    
    
  
  
    
    
  

   
     
     
   当区间的定义是左闭右闭区间[left,right]时：
  
    
    
  
  
    
    
  

   
     
     
   如果target小于mid所指向的值，则表示接下来要在左半部分查找，这时由于mid所指的值已经考察过了，所以right=mid-1，即新的区间是[left,mid-1]；
  
    
    
  
  
    
    
  

   
     
     
   如果target大于mid所指向的值，则表示接下来要在右半部分查找，这时由于mid所指的值已经考察过了，所以left=mid+1，即新的区间是[mid+1,right]。
  
    
    
  
   
     
     
   

    
      
      
    当区间的定义是左闭右开区间[left,right)时：
   
     
     
   
   
     
     
   

    
      
      
    如果target小于mid所指向的值，则表示接下来要在左半部分查找，这时由于mid所指的值已经考察过了，新一轮的搜索中mid所指的值不用考察，所以right=mid，即新的区间是[left,mid)；
   
     
     
   
   
     
     
   

    
      
      
    如果target大于mid所指向的值，则表示接下来要在右半部分查找，这时由于mid所指的值已经考察过了，而区间左边是闭区间，所以left=mid+1，即新的区间是[mid+1,right)。
   
     
     
   
  
    
    
  

   
     
     
   接着，基于这两种区间的定义，我们看下如何用二分查找法解答该题目。
  
    
    
  
  
    
    
  

   
     
     
   

  
    
    
  
01
左闭右闭区间[left,right]
  
    
    
  

   
     
     
   基于上述的分析，我们知道对于左闭右闭区间来说，循环结束时，left>right。由于，数组是升序排好的，所以当目标值在数组中不存在时，left所指向的位置即为目标值应该插入的位置。
  
    
    
  
  
    
    
  

   
     
     
   具体可参考如下动画演示：
  
    
    
  
  
    
    
  

   
     
     
   
   
     
     
   Play
  
    
    
  
代码实现：
‍
  
    
    
  

   
     
     
   

  
    
    
  
02
左闭右开区间[left,right)
   
     
     
   

    
      
      
    基于上述的分析，我们知道对于左闭右开区间来说，循环结束时，left==right。这时由于left==right，所以当目标值在数组中不存在时，left或right所指向的位置即为目标值应该插入的位置。
   
     
     
   
   
     
     
   

    
      
      
    具体可参考如下动画演示：
   
     
     
   
   
     
     
   

    
      
      
    
    
      
      
    Play
   
     
     
   
代码实现：

   
     
     
   

    
      
      
    

   
     
     
   

-End-

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！