21xrx.com
2024-11-05 18:28:43 Tuesday
登录
文章检索 我的文章 写文章
C++二分查找代码
2023-06-28 07:44:32 深夜i     --     --
C++ 二分查找 代码

二分查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。

二分查找算法的基本思想是:

先确定待查关键字所在的区间,然后逐步缩小区间的范围直到找到给定的关键字为止。具体实现时,设查找区间的起始位置为left,终止 位置为right,中间位置为mid,每次取mid等于left和right的中点,然后将待查关键字与mid位置的元素进行比较,如果两者相等,则查找成功;如果待查关键字小于mid位置的元素,说明待查元素可能在left~mid-1之间,则将查找区间缩小至left~mid-1;如果待查关键字大于mid位置的元素,说明待查元素可能在mid+1~right之间,则将查找区间缩小至mid+1~right。若查找区间为空,则表明待查元素不存在于数组中。

下面是C++实现二分查找的代码:

int binary_search(int arr[], int n, int key)

{

  int left = 0, right = n - 1;

  while (left <= right)

  {

    int mid = (left + right) / 2;

    if (arr[mid] == key)

      return mid;

    else if (arr[mid] < key)

      left = mid + 1;

    else

      right = mid - 1;

  }

  return -1;

}

代码中,arr[]为有序数组,n为数组大小,key为待查关键字。该函数的返回值为待查关键字在数组中的下标,若关键字不在数组中,则返回-1。

在使用该函数时,需要先将数组进行排序,使得数组中的元素保持有序。可以使用C++标准库中的sort函数实现排序,代码如下:

sort(arr, arr + n);

使用该算法时需要注意,二分查找只适用于有序数组,如果数组未排序,需要先进行排序;另外,二分查找对内存的占用非常小,适用于大数据快速查找。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复