devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

查找算法--01 顺序查找和二分查找_顺序查找 二分法

作者：从前慢现在也慢 | 2024-05-24 10:11:32

赞

踩

顺序查找 二分法

目      录

1. 顺序查找

1.1 顺序查找介绍

1.2 顺序查找适用范围

1.3 顺序查找代码实现

2.二分查找

2.1 二分查找介绍

2.2 二分查找适用范围

2.3 二分查找代码实现

2.3.1 二分查找简单代码实现

2.3.2 二分查找代码优化-查找左端元素-代码实现

2.3.3 二分查找代码优化-查找右端元素-代码实现

2.3.4 二分查找代码优化-减少不必要的查找

 2.3.5 二分查找代码优化-对于不在数列中的元素寻找最接近的值

 2.3.6 二分查找代码优化-找一个适合插入新元素的地址

1. 顺序查找

1.1 顺序查找介绍

        顺序查找是最常见也是最朴素的查找思想，即按顺序比较一个有序或者无序的数列的每个元素，直到找到关键字为止。

1.2 顺序查找适用范围

        它非常简单，适用于一个有序或者无序的数列。时间复杂度：O(n)

1.3 顺序查找代码实现

       # 顺序查找，找到就返回所在地址，找不到返回 -1
       # 可以看到如果存在多个相同元素，那么找到的第一个即返回

  1. import random
  2. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,100]
  3. random.shuffle(a)
  4. print("shuffled list ==>",a)
  5.  
  6. # 顺序查找，找到就返回所在地址，找不到返回 -1
  7. # 可以看到如果存在多个相同元素，那么找到的第一个即返回
  8. def SequentiaSearch(nums,obj):
  9.     nums_len=len(nums)
  10.     i=0
  11.     while(i<nums_len):
  12.         if(nums[i]==obj):
  13.             return(i)
  14.         i+=1
  15.     return(-1)
  16. obj_list=list(set(a))
  17. obj_list.extend([-100,99,101])
  18. print("obj_list is ==>",obj_list)
  19.  
  20. for ele in obj_list:
  21.     print(ele,SequentiaSearch(a,ele))

运行结果

2.二分查找

2.1 二分查找介绍

        二分查找是非常常见的查找算法：

  1. 把有序的数列根据首尾和中间元素分为两段；首到中间元素是左段，中间元素到尾是右端。
  2. 查找中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
  3. 如果查找的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
  4. 如果到最后查找范围缩小到空页没有找到，则意味没有，可以返回为-1
  5. 否则返回找到的元素地址

2.2 二分查找适用范围

        它适用于一个有序（正序和反序不限）的数列。时间复杂度：O(log2n)。在有序的数列里面，它的查找速度远大于顺序查找。

2.3 二分查找代码实现

2.3.1 二分查找简单代码实现

        # 这个算法非常简单，只是在正序的列表中查找某个元素
        # 如果查找到，则返回该元素的所在位置，
        # 如果相同的元素有多个，那么返回的则是找到的第一个符合要求的元素的位置。

        请注意：这里说寻找序列里面的第一个符合要求的元素的位置，不是指在数列里面第一个元素的位置。

这段是设计的简单的二分查找代码，面向的是正序的数列，如果是反序的数列，依样画葫芦颠倒一下比较顺序就好。

  1. # 这个算法非常简单，只是在正序的列表中查找某个元素
  2. # 如果查找到，则返回该元素的所在位置，
  3. # 如果相同的元素有多个，那么返回的则是找到的第一个符合要求的元素的位置
  4. def half_seek(nums,obj):
  5.     left=0
  6.     right=len(nums)-1
  7.     # 
  8.     while(left<=right):
  9.         # 中间的元素地址
  10.         mid=(left+right)//2
  11.         
  12.         # 如果找到一个符合要求的，即可返回元素所在地址
  13.         if(nums[mid]==obj):
  14.             return(mid)
  15.         elif(nums[mid]<obj):
  16.             left=mid+1    
  17.         else:
  18.             right=mid-1
  19.     return(-1)

这段是测试代码

  1. import copy
  2. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,100]
  3. b=[-1,88,13]
  4. b.extend(list(set(a)))
  5. b.append(100)
  6. b.append(101)
  7. print(a)
  8. print("*"*90)
  9. print(b)
  10. print("*"*90)
  11. # f 是我用来设计和 half_seek 做比较的函数
  12. # f 是利用 Python3 内置方法 index 实现的顺序查找方法 
  13. f=lambda x,y:x.index(y) if y in x else -1 
  14. for tmp in b:
  15.     print(tmp,half_seek(a,tmp),f(a,tmp))

 下面是使用测试代码得到的运行结果

        从运行结果可以看出，针对在数列或者不在数列中的元素，该函数都能返回正确的结果。但是针对元素9、10，简单二分查找算法返回的元素地址和顺序查找返回的地址是不一样的，这是因为数列中存在多个相同的元素。

        那么在这样一种情况下，用户可能不介意是数列中第几个符合条件的元素被返回，也可能有一定的要求。最常见的是：

        1）返回数列中第一个符合条件的元素，

        2）返回数列中最后一个符合条件的元素。

2.3.2 二分查找代码优化-查找左端元素-代码实现

        如果一个正序的数列里面，存在多个相同的元素，那么返回数列中第一个符合条件的元素，也可以理解为查找左端元素。

        代码实现如下：

  1. # 这个二分查找算法如果相同的元素有多个，
  2. # 那么返回的则是找到的第一个符合要求的位置（左侧）
  3. def half_seek_left(nums,obj):
  4.     left=0
  5.     right=len(nums)-1
  6.     found=-1
  7.     # 
  8.     while(left<=right):
  9.         # 中间的元素地址
  10.         mid=(left+right)//2
  11.         # 如果找到一个符合要求的，继续向左去搜索
  12.         if(nums[mid]==obj):
  13.             found=mid        #注意这里用了一个 found 来记录已经找到的地方
  14.             print("mid is found in place==>",found)
  15.             right=mid-1  # 这里不是直接返回而是继续向左查找
  16.         elif(nums[mid]<obj):
  17.             left=mid+1    
  18.         else:
  19.             right=mid-1
  20.     print("left is {0} and right is {1}!".format(left,right))
  21.     return(found)

测试代码如下

  1. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,100]
  2. b=[-1,88,13]
  3. b.extend(list(set(a)))
  4. b.append(100)
  5. b.append(101)
  6. print(a)
  7. print("*"*90)
  8. print(b)
  9. print("*"*90)
  10. # f 是我用来设计和 half_seek 做比较的函数
  11. # f 是利用 Python3 内置方法 index 实现的顺序查找方法 
  12. f=lambda x,y:x.index(y) if y in x else -1 
  13. for tmp in b:
  14.     print(tmp,half_seek_left(a,tmp),f(a,tmp))

运行结果如下：

        根据上面的运行结果可以看到，所有在数列的中的元素都被找到，并且返回左侧端的元素，和对应的 f 函数返回值一样；对于不在数列中的元素则返回了 -1。测试代码中打印出了 mid 符合条件的元素依次被找到的情况，如果不使用 found 来记录符合条件的 mid 元素，那么在继续寻找时候可能会丢失符合条件的元素信息。  

2.3.3 二分查找代码优化-查找右端元素-代码实现

        如果一个正序的数列里面，存在多个相同的元素，那么返回数列中最后个符合条件的元素，也可以理解为查找右端元素。

        代码实现如下：

  1. # 这个二分查找算法如果相同的元素有多个，
  2. # 那么返回的则是找到的最后一个符合要求的位置（右侧）
  3. def half_seek_right(nums,obj):
  4.     left=0
  5.     right=len(nums)-1
  6.     found=-1
  7.     # 
  8.     while(left<=right):
  9.         # 中间的元素地址
  10.         mid=(left+right)//2
  11.         # 如果找到一个符合要求的，继续向右去搜索
  12.         if(nums[mid]==obj):
  13.             found=mid   #注意这里用了一个 found 来记录已经找到的地方
  14.             print("mid is found in place==>",found)
  15.             left=mid+1  # 这里不是直接返回而是继续向右查找
  16.         elif(nums[mid]<obj):
  17.             left=mid+1    
  18.         else:
  19.             right=mid-1
  20.     print("left is {0} and right is {1}!".format(left,right))
  21.     return(found)

 测试代码如下

  1. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,100]
  2. b=[-1,88,13]
  3. b.extend(list(set(a)))
  4. b.append(101)
  5. f=lambda x,y:x.index(y) if y in x else -1 
  6. print(a)
  7. print("*"*90)
  8. print(b)
  9. print("*"*90)
  10. for tmp in b:
  11.     print("*"*50)
  12.     print(tmp,half_seek_right(a,tmp),f(a,tmp))

测试代码运行结果如下：

 运行结果符合预期。

2.3.4 二分查找代码优化-减少不必要的查找

        以简单的二分查找为例，我在代码上加上 print 语句，可以看到当查找的元素不在数列中时候，代码也傻乎乎的查询和比对了很多次。

        当前代码如下：

  1. # 这个算法非常简单，只是在正序的列表中查找某个元素
  2. # 如果查找到，则返回该元素的所在位置，
  3. # 如果相同的元素有多个，那么返回的则是找到的第一个符合要求的位置
  4. def half_seek(nums,obj):
  5.     left=0
  6.     right=len(nums)-1
  7.     # 
  8.     while(left<=right):
  9.         # 中间的元素地址
  10.         mid=(left+right)//2
  11.         print("current mid is {0}".format(mid))
  12.         # 如果找到一个符合要求的，即可返回元素所在地址
  13.         if(nums[mid]==obj):
  14.             return(mid)
  15.         elif(nums[mid]<obj):
  16.             left=mid+1    
  17.         else:
  18.             right=mid-1
  19.     return(-1)
  20. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,100]
  21. half_seek(a,101)

 运行结果可以看出，对于有序数列，即使被查找的元素一看就是大于数列中的最大值或者小于数列中的最小值，算法还是把数列翻了个底朝天，然后才返回 -1。 

 

 对于这种情况，尤其是查找次数非常多，不在数列中的情况非常普遍时候，是很影响性能的。

 所以建议这时候可以做个优化，在二分查找前就做个判断。代码实现如下：

  1. # 这个算法非常简单，只是在正序的列表中查找某个元素
  2. # 如果查找到，则返回该元素的所在位置，
  3. # 如果相同的元素有多个，那么返回的则是找到的第一个符合要求的位置
  4. def half_seek(nums,obj):
  5.     left=0
  6.     right=len(nums)-1
  7.     if( obj < nums[0] or obj >nums[-1]):
  8.         return(-1)
  9.     # 
  10.     while(left<=right):
  11.         # 中间的元素地址
  12.         mid=(left+right)//2
  13.         print("current mid is {0}".format(mid))
  14.         # 如果找到一个符合要求的，即可返回元素所在地址
  15.         if(nums[mid]==obj):
  16.             return(mid)
  17.         elif(nums[mid]<obj):
  18.             left=mid+1    
  19.         else:
  20.             right=mid-1
  21.     return(-1)
  22. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,100]
  23. half_seek(a,101)

运行结果可以很清楚的看到，减少了 5 次 即 

 2.3.5 二分查找代码优化-对于不在数列中的元素寻找最接近的值

        很多时候我们用二分查找如果找不到只返回 -1 这个地址是不够的，我们知道一个最接近这个元素的值是多少。

        代码实现如下：

  1. # 这个算法非常简单，只是在正序的列表中查找某个元素
  2. # 如果查找到，则返回该元素的所在位置，
  3. # 如果相同的元素有多个，那么返回的则是找到的第一个符合要求的位置
  4. # 如果没有合适的元素，则比较left right 两个位置的元素到底谁更贴近目标
  5. def half_seek_nearest(nums,obj):
  6.     left=0
  7.     right=len(nums)-1
  8.     # 考虑目标数小于列表最小数的情况
  9.     if( obj < nums[0] ):
  10.         return(left)
  11.  
  12.     # 考虑目标数大于列表最大数的情况
  13.     if(obj >nums[-1]):
  14.         return(right)
  15.     # 
  16.     while(left<=right):
  17.         # 中间的元素地址
  18.         mid=(left+right)//2
  19.         # 如果找到一个符合要求的，即可返回元素所在地址
  20.         if(nums[mid]==obj):
  21.             print("Searching {0},found address is {1} and nearest ele is {2}".format(obj,mid,nums[mid]))
  22.             return(mid)
  23.         elif(nums[mid]<obj):
  24.             left=mid+1    
  25.         else:
  26.             right=mid-1
  27.     
  28.     # 因为前面考虑了目标数过大或者过小情况，所以不需要考虑 left、right 越界的情况
  29.     if(abs(nums[left]-obj)<=abs(nums[right]-obj)):
  30.         found=left
  31.     else:
  32.         found=right
  33.     print("Searching {0},found address is {1} and nearest ele is {2}".format(obj,found,nums[found]))
  34.     return(found)

测试代码如下：

  1. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,70,82,100]
  2. b=[-1,13,8,13,14,15,20,21,88,99,]
  3. b.extend(list(set(a)))
  4. f=lambda x,y:x.index(y) if y in x else -1 
  5. print(a)
  6. print("*"*90)
  7. print(b)
  8. print("*"*90)
  9.  
  10. # f 是我用来设计和 half_seek 做比较的函数
  11. # f 是利用 Python3 内置方法 index 实现的顺序查找方法 
  12. f=lambda x,y:x.index(y) if y in x else -1 
  13. for tmp in b:
  14.     print("-"*50)
  15.     print(tmp,half_seek_nearest(a,tmp),f(a,tmp))

 运行结果让人满意：

下面这段代码也可以实现相关功能，但是和上面代码性能的优缺点在于数据的特点。

如果数据列表很长，并且查找的数据有很多不在列表内，那么使用上面的算法，先判断是否在列表内，再二分查找；毕竟列表长度越长，每次查找的时间也越长。

如果查找的数据很少不在列表内，那么就先二分查找再避免每次查一个数据都要先比较最小值和最大值。

  1. def half_seek_nearest2(nums,obj):
  2.     left=0
  3.     right=len(nums)-1
  4.     # 
  5.     while(left<=right):
  6.         # 中间的元素地址
  7.         mid=(left+right)//2
  8.         # 如果找到一个符合要求的，即可返回元素所在地址
  9.         if(nums[mid]==obj):
  10.             #print("Searching {0},found address is {1} and nearest ele is {2}".format(obj,mid,nums[mid]))
  11.             return(mid)
  12.         elif(nums[mid]<obj):
  13.             left=mid+1    
  14.         else:
  15.             right=mid-1
  16.     
  17.     # 考虑obj 大于最大数
  18.     if(left>len(nums)-1):
  19.         found=len(nums)-1
  20.     # 考虑obj 小于最小数
  21.     elif(right<0):
  22.         found=0
  23.     # 考虑最后一次比较是向右挪动
  24.     elif(left>mid):
  25.         if(abs(nums[left]-obj)<abs(nums[mid]-obj)):
  26.             found=left
  27.         else:
  28.             found=mid
  29.     # 考虑最后一次比较是向左挪动
  30.     else:
  31.         if(abs(nums[right]-obj)<=abs(nums[mid]-obj)):
  32.             found=right
  33.         else:
  34.             found=mid
  35.  
  36.     return(found)

 2.3.6 二分查找代码优化-找一个适合插入新元素的地址

        很多时候我们用二分查找是为了排序，我们需要在数列中插入一个新元素。在这种情况下，没找到相同的元素很正常，但是我们要找到一个合适的位置插入新元素，这时候如果找不到只返回 -1 这个地址是不够的，我们需要返回能插入的地址。

        这时候就需要将问题转换成找到一个元素小于等于搜索的元素且最接近搜索的元素，并且考虑到插入算法的稳定性和减少挪动元素的概率，问题就转换成找一个元素小于等于搜索的元素且最接近搜索的元素，如果有多个相同的元素符合要求，那么找最右侧的元素。

        代码实现：

  1. # 这个算法非常简单，只是在正序的列表中插入某个元素
  2. # 如果查找到有相同的元素，然后插入在相同元素的最右端
  3. # 如果没有合适的元素，则插入在小于该元素的最大元素后面即可
  4. def half_seek_forInsert(nums,obj):
  5.     left=0
  6.     right=len(nums)-1
  7.     found=-1
  8.     
  9.     if( obj < nums[0] ):
  10.         found=left
  11.     elif(obj >nums[-1]):
  12.         found=len(nums)
  13.     else:
  14.         while(left<=right):
  15.             mid=(left+right)//2 # 中间的元素地址
  16.             
  17.             # 
  18.             if(nums[mid]==obj):
  19.                 found=mid  #先记录这个查找到的地方
  20.                 left=mid+1 #继续向右查找
  21.             elif(nums[mid]<obj):
  22.                 left=mid+1    
  23.             else:
  24.                 right=mid-1
  25.     
  26.         # 如果没有找到，但是left和right肯定是在要插入的元素附近
  27.         if(found==-1):
  28.             if((nums[left] <obj) and (nums[right] <obj)):
  29.                 found=left if left>right else right
  30.             elif((nums[left] >obj) and (nums[right] >obj)):
  31.                 found=left if left<=right else right
  32.             else:
  33.                 found=left if left>=right else right
  34.     
  35.     #将数据往后移动，空出 found 处填入 obj
  36.     nums.append("end")
  37.     k=len(nums)-1
  38.     while(k>found):
  39.         nums[k]=nums[k-1]
  40.         k-=1
  41.     nums[k]=obj
  42.     return(nums)

这是一段测试代码，主要是测试插入的元素已经在数列中有的这种情况。

  1. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,70,82,100]
  2. b=list(set(a))
  3.  
  4. for tmp in b:
  5.     print("-"*90)
  6.     a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,70,82,100]
  7.     print(a,tmp)
  8.     print(half_seek_forInsert(a,tmp))

运行情况：

 这是另外一段测试代码，主要是测试插入的元素不在数列中有的这种情况。

  1. a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,70,82,100]
  2. b=[-1,-2,2,5,6,8,13,13,14,15,16,20,21,67,68,69,88,99,101,102]
  3.  
  4.  
  5. for tmp in b:
  6.     print("-"*90)
  7.     a=[0, 1, 3, 4, 4, 7, 9, 9,9,9,10,10,10,10, 11, 12,66,70,82,100]
  8.     print(a,tmp)
  9.     print(half_seek_forInsert(a,tmp))

 运行情况：

'''

要是大家觉得写得还行，麻烦点个赞或者收藏吧，想个博客涨涨人气，非常感谢！

更欢迎大家一起来讨论，共同学习进步！

'''

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/616972
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号