一、简述

二分查找是一种在有序数组中查找特定元素的高效算法，其时间复杂度为 O(log n)。

二、详细代码

#include<iostream>
#include<cmath>
using namespace std;int BinarySearch(int arr[], int x, int size )
{int l = 0;int r = size-1;int m = 0;while( l <= r){m = floor((l + r)/2);if( arr[m] == x){return m;} else if(arr[m] > x){r = m - 1;}else{l = m + 1;}}return -1;}int main()
{int size;std::cout<<"Enter Size:";std::cin>>size;int* arr = new int[size];for( int i = 0; i < size; i++){cout<<"arr element:";cin>>arr[i];}int x;cout<<"X:";cin>>x;int j = BinarySearch( arr,  x, size);if(j != -1){cout<<j;}else{cout<<0;}delete[] arr;return 0;
}

三、主要逻辑说明

• 参数说明：
  • arr[]：待查找的有序数组。
  • x：要查找的目标元素。
  • size：数组的大小。
• 函数实现：
  • 初始化变量 l 为 0，表示数组的左边界；r 为 size - 1，表示数组的右边界；m 为 0，用于存储中间元素的索引。
  • 使用 while 循环，只要左边界 l 小于等于右边界 r，就继续查找。
  • 在每次循环中，计算中间元素的索引 m，使用 floor 函数向下取整。
  • 如果中间元素 arr[m] 等于目标元素 x，则返回中间元素的索引 m。
  • 如果中间元素 arr[m] 大于目标元素 x，说明目标元素在左半部分，更新右边界 r 为 m - 1。
  • 如果中间元素 arr[m] 小于目标元素 x，说明目标元素在右半部分，更新左边界 l 为 m + 1。
  • 如果循环结束后仍未找到目标元素，返回 -1。