二分查找算法c++代码
概述
二分查找，又称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。该算法的核心思想是将待查找区间不断缩小一半，直到找到该元素或确认该元素不存在。因为每一次查找都是将搜索区间减半，所以算法的时间复杂度是O(logN)。
算法实现
下面给出二分查找算法的c++代码实现：
```
int binary_search(int arr[], int n, int target)
{
int left = 0, right = n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
```
该算法接收一个有序数组、数组长度和目标元素，返回该元素在数组中的下标。如果该元素不存在，则返回-1。
要点分析
1. 循环条件
使用while循环时，循环结束的条件是left>right，但是因为每次计算mid时会向下取整，所以需要使用left<=right。
2. 中间元素的计算
使用 mid = left + (right - left) / 2 计算中间元素时，可以避免left+right可能溢出的问题。也可以使用 mid = (left + right) >> 1。
3. 当元素不存在时，返回值为-1
如果查找到最后，left>right，即找不到该元素时，需要返回-1。
4. 适用范围
二分查找算法只适用于有序数组。对于无序数组，需要先进行排序。
5. 变种
在有些情况下，需要查找第一个等于目标元素的位置，还有一种情况是查找最后一个等于目标元素的位置。这两种变种的代码如下。
```
int binary_search_first(int arr[], int n, int target)
{
int left = 0, right = n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
if (mid == 0 || arr[mid - 1] != target)
return mid;
else
right = mid - 1;
}
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int binary_search_last(int arr[], int n, int target)
{
int left = 0, right = n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
if (mid == n - 1 || arr[mid + 1] != target)
return mid;
else
left = mid + 1;
}
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
```
