I have a date with Algorthim - 分治之二分搜索

小灰灰 2022-06-17 08:46 129阅读 0赞

BinarySearch

I have a date with Algorthim


  • 定义:
  1. * 在计算机科学中, 二分搜索(binary search), 也称折半搜索(half-interval search)、对数搜索(logarithmic search), 是一种在**有序数组**中查找某一特定元素的搜索算法.
  2. * 搜索过程从数组的**中间元素**开始, 如果中间元素正好是要查找的元素, 则搜索过程结束;
  3. * 如果某一特定元素大于或者小于中间元素, 则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较.
  4. * 如果在某一步骤**数组为空**, 则代表找不到.(也就代表遍历完整个数组也没有找到这个元素).
  5. * 这种搜索算法**每一次**比较都使**搜索范围缩小一半**.

BinarySearch

  • 解析步骤:
  1. * 给予一个包含n个带值元素的数组A或是记录`A0 ... An−1`, 使得`A0 ≤ ... ≤ An−1`(有序数组), 以及目标值`T`,还有下列用来搜索TA中位置的子程序.
  2. * a. `L`0, `R`n 1.
  3. * b. 如果`L > R`, 则搜索以失败告终.
  4. * c. `m`(中间值元素)为`(L + R) / 2`加上下**高斯符号**.
  5. * d. 如果`Am < T`, Lm + 1并回到步骤二.
  6. * e. 如果`Am > T`, Rm - 1并回到步骤二.
  7. * f. `Am = T`, 搜索结束: 回传值m.
  8. * 这个迭代步骤会持续通过两个变量追踪搜索的边界.
  9. * 有些实际应用会在算法的最后放入相等比较, 让比较循环更快, 但平均而言会多一层迭代.
  10. * 这时候需要联想分治的思想, 分解的`子问题`之间`相互独立`且与`原问题的形式相同`.
  11. * 最重要的就是`子问题的合并`可以得到原问题的解.

  • 大致匹配:
  1. * 以上程序只适用于完全匹配, 也就是查找一个目标值的位置.
  2. * 不过,因为有序数组的顺序性,将二分搜索算法扩展到能适用大致匹配并不是很重要.
  3. * 举例来说, 二分搜索算法可以用来计算一个赋值的排名(或称秩, 比它更小的元素的数量)、前趋(下一个最小元素)、后继(下一个最大元素)以及最近邻.
  4. * 搜索两个值之间的元素数目的范围查询可以借由两个排名查询(又称秩查询)来运行.
  5. * 排名查询可以使用调整版的二分搜索来运行.
  6. * 借由在成功的搜索回传`m`, 以及在失败的搜索回传`L`, 就会取而代之地回传了比起目标值小的元素数目.
  7. * `前趋``后继`查询可以借由排名查询来运行.
  8. * 一旦知道目标值的排名, 其前趋就会是那个位于其排名位置的元素(因为它是小于目标值的最大元素).
  9. * 其后继是(数组中的)下一个元素, 或是(非数组中的)前趋的下一个元素.
  10. * 目标值的最近邻可能是前趋或后继, 取决于何者较为接近.
  11. * 范围查询也是直接了当的.
  12. * 一旦知道两个值的排名, `不小于第一个值且小于第二个值的元素`数量就会是两者排名的差.
  13. * 这个值可以根据范围的端点是否算在范围内, 或是数组是否包含其端点的对应键来增加或减少1.

  • 复杂度分析:
  1. * 时间复杂度
  2. * 折半搜索每次把搜索区域减少一半, 时间复杂度为 O(log n).(n代表集合中元素的个数)
  3. * 空间复杂度
  4. * O(1).
  5. * 虽以递归形式定义, 但是尾递归, 可改写为循环.

  • 示例代码:

    // 递归版本

    1. int binary_search(const int arr[], int start, int end, int khey) {
    2. if (start > end) // 上面的L > R
    3. return -1;
    4. int mid = start + (end - start) / 2; //直接平均可能會溢位,所以用此算法
    5. if (arr[mid] > khey)
    6. return binary_search(arr, start, mid - 1, khey);
    7. if (arr[mid] < khey)
    8. return binary_search(arr, mid + 1, end, khey);
    9. return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
    10. }

    // while循环

    1. int binary_search(const int arr[], int start, int end, int khey) {
    2. int mid;
    3. while (start <= end) {
    4. mid = start + (end - start) / 2; //直接平均可能會溢位,所以用此算法
    5. if (arr[mid] < khey)
    6. start = mid + 1;
    7. else if (arr[mid] > khey)
    8. end = mid - 1;
    9. else
    10. return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
    11. }
    12. return -1;
    13. }

    //javascript版本

    1. Array.prototype.binary_search = function(low, high, khey) {
    2. if (low > high)
    3. return -1;
    4. var mid = parseInt((high + low) / 2);
    5. if (this[mid] > khey)
    6. return this.binary_search(low, mid - 1, khey);
    7. if (this[mid] < khey)
    8. return this.binary_search(mid + 1, high, khey);
    9. return mid;
    10. };

    python版本

    1. def binary_search(arr,start,end,hkey):
    2. if start > end:
    3. return -1
    4. mid = start + (end - start) / 2
    5. if arr[mid] > hkey:
    6. return binary_search(arr, start, mid - 1, hkey)
    7. if arr[mid] < hkey:
    8. return binary_search(arr, mid + 1, end, hkey)
    9. return mid

    //c#版本

    1. static int binary_search(int[] arr, int start, int end, int khey)
    2. {
    3. int mid;
    4. while (start <= end)
    5. {
    6. mid = (start + end) / 2;
    7. if (arr[mid] < khey)
    8. start = mid + 1;
    9. else if (arr[mid] > khey)
    10. end = mid - 1;
    11. else
    12. return mid;
    13. }
    14. return -1;
    15. }

JackDan9 Thinking.
JackDan9 with Algorthim.


谢谢您阅读我的博客!

发表评论

表情:
评论列表 (有 0 条评论,129人围观)

还没有评论,来说两句吧...

相关阅读