二进制搜索的Python程序（递归和迭代）-yiteyi-C++库

简言之，这种搜索算法利用了一组元素，这些元素在仅仅一次比较后就忽略了一半的元素。

null

将x与中间的元素进行比较。
如果x与中间元素匹配，则返回中间索引。
否则，如果x大于中间元素，则x只能位于中间元素后的右（大）半子阵列中。然后我们对右半部分再次应用算法。
否则，如果x较小，则目标x必须位于左（下）半部分。所以我们对左半部分应用算法。

递归：

Python3

                         # Python 3 program for recursive binary search.                       
                         # Modifications needed for the older Python 2 are found in comments.                       
           
                         # Returns index of x in arr if present, else -1                       
                         def                                     binary_search(arr, low, high, x):                       
           
                                                 # Check base case                       
                                                 if                                     high >                                     =                                     low:                       
           
                                                 mid                                     =                                     (high                                     +                                     low)                                     /                                     /                                     2                       
           
                                                 # If element is present at the middle itself                       
                                                 if                                     arr[mid]                                     =                                     =                                     x:                       
                                                 return                                     mid                       
           
                                                 # If element is smaller than mid, then it can only                       
                                                 # be present in left subarray                       
                                                 elif                                     arr[mid] > x:                       
                                                 return                                     binary_search(arr, low, mid                                     -                                     1                                     , x)                       
           
                                                 # Else the element can only be present in right subarray                       
                                                 else                                     :                       
                                                 return                                     binary_search(arr, mid                                     +                                     1                                     , high, x)                       
           
                                                 else                                     :                       
                                                 # Element is not present in the array                       
                                                 return                                     -                                     1                       
           
                         # Test array                       
                         arr                                     =                                     [                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     10                                     ,                                     40                                     ]                       
                         x                                     =                                     10                       
           
                         # Function call                       
                         result                                     =                                     binary_search(arr,                                     0                                     ,                                     len                                     (arr)                                     -                                     1                                     , x)                       
           
                         if                                     result !                                     =                                     -                                     1                                     :                       
                                                 print                                     (                                     "Element is present at index"                                     ,                                     str                                     (result))                       
                         else                                     :                       
                                                 print                                     (                                     "Element is not present in array"                                     )                       

输出：

Element is present at index 3

迭代：

Python3

                         # Iterative Binary Search Function                       
                         # It returns index of x in given array arr if present,                       
                         # else returns -1                       
                         def                                     binary_search(arr, x):                       
                                                 low                                     =                                     0                       
                                                 high                                     =                                     len                                     (arr)                                     -                                     1                       
                                                 mid                                     =                                     0                       
           
                                                 while                                     low <                                     =                                     high:                       
           
                                                 mid                                     =                                     (high                                     +                                     low)                                     /                                     /                                     2                       
           
                                                 # If x is greater, ignore left half                       
                                                 if                                     arr[mid] < x:                       
                                                 low                                     =                                     mid                                     +                                     1                       
           
                                                 # If x is smaller, ignore right half                       
                                                 elif                                     arr[mid] > x:                       
                                                 high                                     =                                     mid                                     -                                     1                       
           
                                                 # means x is present at mid                       
                                                 else                                     :                       
                                                 return                                     mid                       
           
                                                 # If we reach here, then the element was not present                       
                                                 return                                     -                                     1                       
           
           
                         # Test array                       
                         arr                                     =                                     [                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     10                                     ,                                     40                                     ]                       
                         x                                     =                                     10                       
           
                         # Function call                       
                         result                                     =                                     binary_search(arr, x)                       
           
                         if                                     result !                                     =                                     -                                     1                                     :                       
                                                 print                                     (                                     "Element is present at index"                                     ,                                     str                                     (result))                       
                         else                                     :                       
                                                 print                                     (                                     "Element is not present in array"                                     )                       

输出：

Element is present at index 3

请参考文章 二进制搜索 更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章