查找算法之二分法搜索算法
二分搜索是一种在已排序的数组中反复将搜索间隔一分为二的搜索算法。二分搜索的思想是利用数组被排序的信息，将时间复杂度降低到O(Log n)。
二叉搜索算法:执行二叉搜索的基本步骤是:
按升序对数组排序。
将低索引设置为数组的第一个元素，高索引设置为数组的最后一个元素。
将中间指数设置为低指数和高指数的平均值。
如果位于中间下标的元素是目标元素，则返回中间下标。
如果目标元素小于中间索引处的元素，则将高索引设置为中间索引- 1。
如果目标元素大于中间下标处的元素，则将低下标设置为中间下标+ 1。
重复步骤3-6，直到找到该元素或很明显该元素不存在
二分搜索算法可以通过以下两种方式实现：迭代法和递归法
迭代法
binarySearch(arr, x, low, high)
repeat till low = high
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
递归方法(递归方法采用分而治之的方法)
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the left side
return binarySearch(arr, x, low, mid - 1)
二叉搜索算法图说明:
逐步二分搜索算法:我们基本上忽略一半的元素后，只是一个比较。
比较x和中间的元素。
如果x与中间元素匹配，则返回中间索引。
如果x大于中间元素，则x只能位于中间元素之后的右半子数组中。对右半部分进行递归。
Else (x更小)对左半部分重复。
以下代码为二分查找的递归C/C++实现:
// C++ program to implement recursive Binary Search
#include
using namespace std;// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{if (r >= l) {int mid = l + (r - l) / 2;// If the element is present at the middle// itselfif (arr[mid] == x)return mid;// If element is smaller than mid, then// it can only be present in left subarrayif (arr[mid] > x)return binarySearch(arr, l, mid - 1, x);// Else the element can only be present// in right subarrayreturn binarySearch(arr, mid + 1, r, x);}// We reach here when element is not// present in arrayreturn -1;
}int main(void)
{int arr[] = { 2, 3, 4, 10, 40 };int x = 10;int n = sizeof(arr) / sizeof(arr[0]);int result = binarySearch(arr, 0, n - 1, x);(result == -1)? cout << "Element is not present in array": cout << "Element is present at index " << result;return 0;
}
输出
Element is present at index 3
二叉搜索的另一种迭代方法
#include
#include
using namespace std;int binarySearch(vector v, int To_Find)
{int lo = 0, hi = v.size() - 1;int mid;// This below check covers all cases , so need to check// for mid=lo-(hi-lo)/2while (hi - lo > 1) {int mid = (hi + lo) / 2;if (v[mid] < To_Find) {lo = mid + 1;}else {hi = mid;}}if (v[lo] == To_Find) {cout << "Found"<< " At Index " << lo << endl;}else if (v[hi] == To_Find) {cout << "Found"<< " At Index " << hi << endl;}else {cout << "Not Found" << endl;}
}int main()
{vector v = { 1, 3, 4, 5, 6 };int To_Find = 1;binarySearch(v, To_Find);To_Find = 6;binarySearch(v, To_Find);To_Find = 10;binarySearch(v, To_Find);return 0;
}
输出
Found At Index 0
Found At Index 4
Not Found
二叉搜索的迭代实现
// C++ program to implement iterative Binary Search
#include
using namespace std;// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{while (l <= r) {int m = l + (r - l) / 2;// Check if x is present at midif (arr[m] == x)return m;// If x greater, ignore left halfif (arr[m] < x)l = m + 1;// If x is smaller, ignore right halfelser = m - 1;}// if we reach here, then element was// not presentreturn -1;
}int main(void)
{int arr[] = { 2, 3, 4, 10, 40 };int x = 10;int n = sizeof(arr) / sizeof(arr[0]);int result = binarySearch(arr, 0, n - 1, x);(result == -1)? cout << "Element is not present in array": cout << "Element is present at index " << result;return 0;
}
输出
Element is present at index 3