分而治之算法分为三个部分

  • 分解原问题为多个子问题。
  • 解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题。
  • 组合这些子问题的解决方式，得到原问题的解。

怎样将二分搜索用分治的方法实现？

分解: 计算mid并搜索数组较小或较大的一半。
解决: 在较小的或较大的一半中搜索值。
合并: 不需要，直接返回索引值。

  1. function binarySearchRecursive(array,value,low,high){
  2.         if(low <= high){
  3.         const mid = Math.floor((low + high) / 2);
  4.         const element = array[mid];
  5.         if(element < value){
  6.                         return binarySearchRecursive(array,value,mid + 1,high);
  7.         }else if(element > value){
  8.             return binarySearchRecursive(array,value,low,mid - 1);
  9.         }else{
  10.             return mid;
  11.         }
  12.     }
  13.     return -1;
  14. }
  17. function binarySearch(array,value){
  18.         const sortedArray = quickSort(array);
  19.       const low = 0;
  20.     const high = sortedArray.length - 1;
  22.     return binarySearchRecursive(array,value,low,high);
  23. }

上面的算法中，有两个函数： binarySearch和binarySearchRecursive。binarySearch进行二分搜索，binarySearchRecursive是分而治之算法。low参数以0传递，将high参数以sortedArray.length - 1传递，在已排序的数组只进行搜索。在计算mid元素的索引值后，我们确定待搜索的值比mid大还是小。如果大或小，将再次调用binarySearchRecursive函数，但是这次，在子数组中进行搜索，改变low或high参数。如果不大不小，表示找到了这个值，这就是一种基本情形。还有一种情况是low比high要大，这表示算法没有找到这个值。