当前位置: 首页> 财经> 访谈 > 公关公司排行_一个网站需要哪些技术_游戏优化是什么意思_太原百度快速排名提升

公关公司排行_一个网站需要哪些技术_游戏优化是什么意思_太原百度快速排名提升

时间:2025/7/10 0:48:01来源:https://blog.csdn.net/weixin_60461563/article/details/143256481 浏览次数:0次
公关公司排行_一个网站需要哪些技术_游戏优化是什么意思_太原百度快速排名提升

        二分查找是一种高效的查找算法,用于在有序数组中定位目标元素的位置。它的核心思想是每次查找时将范围缩小一半。

题目要求

        实现一个二分查找算法。给定一个递增排序的整型数组 arr 和一个目标值 target,编写一个函数 binarySearch,若 target 存在于 arr 中,则返回其索引;否则返回 -1。算法的时间复杂度要求为 O(log n),适用于有序数组的查找。

        示例:

输入: arr = [1, 2, 4, 5, 7, 8, 9], target = 5
输出: 3输入: arr = [1, 2, 4, 5, 7, 8, 9], target = 3
输出: -1

做题思路

        二分查找是一种在 有序数组 中查找元素的高效方法,通过每次将查找范围缩小一半,使得查找效率达到 O(log n)。这个算法适用于有序数组,且每次查找步骤都是在查找范围的中间值进行判断:

  1. 确定查找范围:定义 left 和 right 两个指针,分别指向数组的起始位置和末尾位置。
  2. 中间元素判断:每次循环中,计算 mid = left + (right - left) / 2。检查 arr[mid] 是否等于目标值 target。
    • 若 arr[mid] == target,则找到目标值并返回 mid。
    • 若 arr[mid] < target,则舍弃左半部分,将 left 更新为 mid + 1,表示在右半部分继续查找。
    • 若 arr[mid] > target,则舍弃右半部分,将 right 更新为 mid - 1,表示在左半部分继续查找。
  3. 返回结果:重复以上步骤直到 left > right。若此时未找到目标值,说明 target 不在数组中。若最终未找到目标值,返回 -1。

运用到的知识点

  1. 数组:理解数组的基本操作。
  2. 指针:使用左右指针来标记查找范围。
  3. 循环和条件判断while循环控制查找过程,条件判断用于判断范围和定位目标值。
  4. 算法时间复杂度分析:二分查找的时间复杂度为 O(log n),适用于有序数据查找。

示例代码

C 实现

#include <stdio.h> // 引入标准输入输出库,用于printf函数  // 二分查找函数,返回目标值的索引,若未找到则返回 -1  
int binarySearch(int arr[], int size, int target) {int left = 0;           // 定义左指针,初始化为数组的第一个元素位置  int right = size - 1;    // 定义右指针,初始化为数组的最后一个元素位置  while (left <= right) {  // 当左指针不超过右指针时,继续执行查找过程  int mid = left + (right - left) / 2; // 计算中间位置,避免直接(left + right) / 2可能导致的整型溢出  if (arr[mid] == target) {  // 如果中间位置的值等于目标值  return mid;            // 找到目标值,返回其索引  }else if (arr[mid] < target) { // 如果中间位置的值小于目标值  left = mid + 1;         // 更新左指针,向右移动一位,在右半部分继续查找  }else {                    // 如果中间位置的值大于目标值  right = mid - 1;        // 更新右指针,向左移动一位,在左半部分继续查找  }}return -1; // 如果循环结束仍未找到目标值,返回-1表示未找到  
}int main() 
{int arr[] = { 1, 2, 4, 5, 7, 8, 9 }; // 定义一个已排序的整数数组  int size = sizeof(arr) / sizeof(arr[0]); // 计算数组的大小,即元素个数  int target = 5; // 定义要查找的目标值  int result = binarySearch(arr, size, target); // 调用二分查找函数,传入数组、大小和目标值,获取查找结果  if (result != -1) { // 如果查找结果不为-1,表示找到了目标值  printf("元素 %d 在索引 %d\n", target, result); // 输出目标值及其索引  }else { // 如果查找结果为-1,表示未找到目标值  printf("元素 %d 未找到\n", target); // 输出未找到目标值的提示  }return 0; // 程序正常结束,返回0  
}

C ++实现

#include <iostream> // 引入输入输出流库,用于输入输出操作  
#include <vector>   // 引入向量库,用于存储动态数组  using namespace std; // 使用标准命名空间,避免每次调用标准库时都需要加std::前缀  // 二分查找函数,接收一个整数向量和目标值,返回目标值的索引,若未找到则返回 -1  
int binarySearch(const vector<int>& arr, int target) {int left = 0;                     // 定义左指针,初始化为0,指向数组的第一个元素  int right = arr.size() - 1;        // 定义右指针,初始化为数组的最后一个元素的索引  while (left <= right) {            // 当左指针不超过右指针时,继续执行循环进行查找  int mid = left + (right - left) / 2; // 计算中间位置索引,避免(left + right)直接相加可能导致的整型溢出  if (arr[mid] == target) {      // 如果中间位置的值等于目标值  return mid;                // 找到目标值,返回其索引  }else if (arr[mid] < target) { // 如果中间位置的值小于目标值  left = mid + 1;             // 更新左指针,向右移动一位,在右半部分继续查找  }else {                        // 如果中间位置的值大于目标值  right = mid - 1;            // 更新右指针,向左移动一位,在左半部分继续查找  }}return -1; // 如果循环结束仍未找到目标值,返回-1表示未找到  
}int main() 
{vector<int> arr = { 1, 2, 4, 5, 7, 8, 9 }; // 定义一个整数向量,并初始化为已排序的数组  int target = 5; // 定义要查找的目标值  int result = binarySearch(arr, target); // 调用二分查找函数,传入向量和目标值,获取查找结果  if (result != -1) { // 如果查找结果不为-1,表示找到了目标值  cout << "元素 " << target << " 在索引 " << result << endl; // 输出目标值及其索引  }else { // 如果查找结果为-1,表示未找到目标值  cout << "元素 " << target << " 未找到" << endl; // 输出未找到目标值的提示  }return 0; // 程序正常结束,返回0  
}

关键字:公关公司排行_一个网站需要哪些技术_游戏优化是什么意思_太原百度快速排名提升

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: