当前位置： 移动技术网 > IT编程>脚本编程>Python > 基础算法——查找(二分法)(python)

基础算法——查找(二分法)(python)

2019年04月30日  | 移动技术网IT编程  | 我要评论

淘算盘,国模嘉妮,纽维t200

基础算法——查找(二分法)(python)。二分查找法(binarysearchst)应用十分广泛，是必须要掌握的查找方法。适用对象是有序数组。具有最优的查找效率和空间需求，能够进行有序相关的操作。但插入操作很慢。

从技巧上来说，二分法适用于含有两个单调相关变化的量的情况，正相关或负相关。其中二分法过程可以抽象出模板，直接迁移套用。

所需变量为区间边界：l、r,数学描述为[l,r);二分中点：mid=（l+r）/2;目标值x：用于决定下一个区间边界。注意l=mid+1或其他方法用于防止陷入死循环。

下面是我自己的总结：

在变换区间边界时，会有以下情况

非增长型：（条件1）l=mid;（条件2）r=mid。（陷入死循环）

过增长型：（条件1）l=mid+1;（条件2）r=mid-1。（容易忽略边界条件有特例）

常增长型：（条件1）l=mid+1;（条件2）r=mid。（只在一种条件下区间边界有增长）

下面举一些例子：

热身(easy)：

278. first bad version

 



class solution(object): def firstbadversion(self, n): """ :type n: int :rtype: int """ l=1 r=n+1 ans=0 while l
 




 


69. sqrt(x)


 


class solution(object):
    def mysqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
#二分法最后返回值是满足边界条件的值中的某一个
#low和high为边界区间，
        low = 0
        high = x+1 #满足数学上左闭右开[low,high) 
        ans=0
        while low < high:
            mid = (low + high) / 2
            if mid ** 2 <=  x:
                ans=mid
                low = mid+1 
            elif mid ** 2 >  x:
                high = mid
        return ans



						

                    

                        

                            
                        

                    

                    


                    
                    

                        
    
                            
  • 
                                
                            
    • 
                        

                    


                    
                    

                    

                        
您可能感兴趣的文章:

                        
                    

                    

                        如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！
                        点击进行留言回复
                    

                

                 
                

                    
相关文章:

                    
                

               
                       
                             

                

                    
                    

                        
                        
                        

                        

                            

                                
                                    
                                
                                 
                                    
                                
                            

                            

                                验证码：
                                
                                    
                                    
                                    
                                
                            

                        

                        
                    

                    
                    

                        
                        
                        
                    

                

            

        

        
        
 
            

                

                    
                    

                    
                


                

                    

                        

                            
最近更新的文章

                            

                                
                            

                        

                    

                


                

                    
                    

                        
                    

                


                

                

                    

                        

                            
大家感兴趣的文章

                            

                                
                            

                        

                    

                

                

                    
                    

                        
                    

                


            

        

    



 


 
 

     
    

        

移动技术网