关于二分查找法
二分查找法主要是解决在“一堆数中找出指定的数”这类问题。
而想要应用二分查找法，这“一堆数”必须有一下特征：
- 存储在数组中
- 有序排列
所以如果是用链表存储的，就无法在其上应用二分查找法了。（曽在面试被问二分查找法可以什么数据结构上使用：数组？链表？）
至于是顺序递增排列还是递减排列，数组中是否存在相同的元素都不要紧。不过一般情况，我们还是希望并假设数组是递增排列，数组中的元素互不相同。
二分查找的基本实现
递归实现
int bsearch(int array[],int low,int high,int target)
{
if(low > high) return -1;
int mid = (low + high)/2;
if(array[mid] > target)
return bsearch(array,mid + 1,high,target);
if(array[mid] < target)
return bsearch(array,low,mid - 1,target)
return mid;
}
非递归实现
int bsearch(int array[],int low,int high,int target)
{
while(low <= high)
{
int mid = (low + high)/2;
if (array[mid] > target)
high = mid - 1;
else if (array[mid] < target)
low = mid + 1;
else //find the target
return mid;
}
//the array does not contain the target
return -1;
}
二分法的题目类型
1.二分法寻找目标值
2.二分法寻找边界值
3.二分法寻找区域