二分查找的简单例题c语言及答案

二分查找也叫折半查找，它是一种在有序数组中查找目标值的算法。这一算法的基本思想是将有序数组分成两半，检查数组中间的元素。如果目标值比中间元素小，则在数组左半部分继续查找；如果目标值比中间元素大，则在数组右半部分继续查找；如果相等，则返回元素下标。二分查找的时间复杂度是O(log n)，是一种高效的查找算法。接下来，我们来看一下一道简单的二分查找例题。

题目描述：

已知一个有序的整数数组nums，给定一个整数target，要求在数组中查找target的下标。如果target存在，返回下标；否则返回-1.

C语言代码及答案：

int binarySearch(int* nums, int numsSize, int target){

int left = 0, right = numsSize - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (nums[mid] == target) {

return mid;

} else if (nums[mid] < target) {

left = mid + 1;

} else {

right = mid - 1;

}

}

return -1;

}

在这段代码中，首先我们定义left为数组左侧下标，right为数组右侧下标，定义mid为数组的中间下标。然后利用while循环进行二分查找。将数组分为左边和右边两部分，每次都判断中间元素和目标元素的大小关系，然后缩小搜索范围再次进行查找，直到找到目标元素或者搜索失败。

接下来我们来分析一下这段代码的优缺点：

优点：

1.时间复杂度低：二分查找的时间复杂度是O(log n)，比线性查找的时间复杂度O(n)更低，因此速度更快。

2.准确性高：二分查找只要能找到解，就一定是准确的，不像线性查找可能会漏掉或者多找一些元素。

3.适用性广：二分查找可以应用于许多不同类型的数据结构，如数组、链表、树等。

缺点：

1.只适用于有序数组：二分查找只能应用于有序数组，如果数组无序，则无法使用。

2.空间复杂度高：每次二分查找都需要存储两个变量，因此空间复杂度相对于线性查找要高。

3.代码实现较复杂：二分查找的实现较为复杂，容易出现一些常见的错误，如死循环等。