# 二分查找法的实现和应用汇总

O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)

• 存储在数组中
• 有序排列

## 二分查找法的基本实现

```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    binarysearch(array, low, mid -1, target);
if (array[mid]< target)
return    binarysearch(array, mid+1, high, target);

//if (midValue == target)
return mid;
}```

```int bsearchWithoutRecursion(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;
}```

## 只用小于比较（<）实现二分查找法

```template <typename T, typename V>
inline int BSearch(T& array, int low, int high, V& target)
{
while(!(high < low))
{
int mid = (low + high)/2;
if (target < array[mid])
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;
}```

## 用二分查找法找寻边界值

在集合中找到一个大于（小于）目标数t的数x，使得集合中的任意数要么大于（小于）等于x，要么小于（大于）等于t。

```int array = {2, 3, 5, 7, 11, 13, 17};
int target = 7;```

### 用二分查找法找寻上届

```//Find the fisrt element, whose value is larger than target, in a sorted array
int BSearchUpperBound(int array[], int low, int high, int target)
{
//Array is empty or target is larger than any every element in array
if(low > high || target >= array[high]) return -1;

int mid = (low + high) / 2;
while (high > low)
{
if (array[mid] > target)
high = mid;
else
low = mid + 1;

mid = (low + high) / 2;
}

return mid;
}```

### 用二分查找法找寻下届

```//Find the last element, whose value is less than target, in a sorted array
int BSearchLowerBound(int array[], int low, int high, int target)
{
//Array is empty or target is less than any every element in array
if(high < low  || target <= array[low]) return -1;

int mid = (low + high + 1) / 2; //make mid lean to large side
while (low < high)
{
if (array[mid] < target)
low = mid;
else
high = mid - 1;

mid = (low + high + 1) / 2;
}

return mid;
}```

`target >= array[high]改为 target > array[high]`

`array[mid] > target改为array[mid] >= target`

## 用二分查找法找寻区域

```//return type: pair<int, int>
//the fisrt value indicate the begining of range,
//the second value indicate the end of range.
//If target is not find, (-1,-1) will be returned
pair<int, int> SearchRange(int A[], int n, int target)
{
pair<int, int> r(-1, -1);
if (n <= 0) return r;

int lower = BSearchLowerBound(A, 0, n-1, target);
lower = lower + 1; //move to next element

if(A[lower] == target)
r.first = lower;
else //target is not in the array
return r;

int upper = BSearchUpperBound(A, 0, n-1, target);
upper = upper < 0? (n-1):(upper - 1); //move to previous element

//since in previous search we had check whether the target is
//in the array or not, we do not need to check it here again
r.second = upper;

return r;
}```

## 在轮转后的有序数组上应用二分查找法

```int SearchInRotatedSortedArray(int array[], int low, int high, int target)
{
while(low <= high)
{
int mid = (low + high) / 2;
if (target < array[mid])
if (array[mid] < array[high])//the higher part is sorted
high = mid - 1; //the target would only be in lower part
else //the lower part is sorted
if(target < array[low])//the target is less than all elements in low part
low = mid + 1;
else
high = mid - 1;

else if(array[mid] < target)
if (array[low] < array[mid])// the lower part is sorted
low = mid + 1; //the target would only be in higher part
else //the higher part is sorted
if (array[high] < target)//the target is larger than all elements in higher part
high = mid - 1;
else
low = mid + 1;
else //if(array[mid] == target)
return mid;
}

return -1;
}```

289 篇文章43 人订阅

0 条评论

## 相关文章

374100

23920

30250

### 算法导论中的四种基本排序

by方阳

14820

17720

53580

### Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

27850

14720

### 【不做标题党，只做纯干货】HashMap在jdk1.7和1.8中的实现

Java集合类的源码是深入学习Java非常好的素材，源码里很多优雅的写法和思路，会让人叹为观止。HashMap的源码尤为经典，是非常值得去深入研究的，jdk1....

12930

14010