二分查找算法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;

}

```