分治法------二分查找

1、首先二分查找满足分治法的四个条件

1）原问题的解可以通过分解为若干个小的问题来解决；（将原数组序列可分解为两个子序列）

2）小的问题的解决方法和原问题的解决方法大致相似；（都是确定一个序列的上界和下界然后求得mid进行比较）

3）小问题的解可以通过合并从而得到原问题的解；（在子序列中可以更容易得到解从而return得出结果）

2、二分法分治法的思维过程

分治法类似于数学归纳法，找出解决问题的数学公式，然后利用公式设计出递归程序

1)求出最简子问题的解

if(arr[mid]==key)

2)分解出子问题的问题的句子

else if (arr[mid] > key) { } else if (arr[mid] < key) { }

3)递归步骤

return BinSearch(arr,key,low,mid-1);

return BinSearch(arr,key,mid+1,high);

下边上代码

int BinSearch(int arr[], int key, int low, int high) { int mid = (low + high) / 2; if (low >= high) { return -1; } if (arr[mid] == key) { return mid; } else if (arr[mid] > key) { return BinSearch(arr,key,low,mid-1); } else if (arr[mid] < key) { return BinSearch(arr,key,mid+1,high); } }