21xrx.com
2024-12-28 08:47:01 Saturday
登录
文章检索 我的文章 写文章
C++代码:顺序查找和二分查找算法的实现
2023-06-24 13:19:37 深夜i     --     --
C++代码 顺序查找 二分查找算法 实现 算法

顺序查找算法:在一个数组中按照顺序循环查找指定的元素,如果找到则返回元素的下标,否则返回-1。

实现代码如下:

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

{

  for (int i = 0; i < n; i++)

  {

    if (arr[i] == key)

      return i;

  }

  return -1;

}

二分查找算法:对于有序数组,在数组中查找指定元素。首先取数组中间位置的元素,如果该元素与要查找的元素相等,则返回该元素的下标。如果要查找的元素小于中间位置的元素,则在数组的左半部分查找;否则在右半部分查找。循环执行以上过程,直到在数组中找到要查找的元素。

实现代码如下:

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

{

  int low = 0, high = n - 1, mid;

  while (low <= high)

  {

    mid = (low + high) / 2;

    if (arr[mid] == key)

      return mid;

    else if (arr[mid] > key)

      high = mid - 1;

    else

    {

      low = mid + 1;

    }

  }

  return -1;

}

总结:

顺序查找和二分查找都是常用的查找算法。当数组元素较少或者无序时,推荐使用顺序查找算法,复杂度为O(n);当数组元素较多且有序时,推荐使用二分查找算法,复杂度为O(logn)。C++语言提供了多种排序和查找函数,需要注意选择合适的算法和函数来提高程序的效率。

  
  

评论区

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