C语言二分查找题目练习

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录题目一、什么是二分查找二、二分法的边界条件三、二分法的写法1、左闭右闭[left, right]a、while (left right)要使用因为left right是有意义的b、if (nums[middle] target) right要赋值为middle - 1因为当前这个nums[middle]不一定是target那么接下来要查找的左区间结束下标位置就是middle - 12、左闭右开[left, right题目leetcode链接https://leetcode.cn/problems/binary-search/给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。示例 1:输入: nums [-1,0,3,5,9,12], target 9输出: 4解释: 9 出现在 nums 中并且下标为 4示例 2:输入: nums [-1,0,3,5,9,12], target 2输出: -1解释: 2 不存在 nums 中因此返回 -1一、什么是二分查找二分查找也称为对半查找是一种在有序数组中查找特定元素的搜索算法。其核心思想是将数组不断对半分割并比较中间值与目标值的大小来缩小搜索范围。如果中间值等于目标值则查找成功如果中间值小于目标值则目标值在数组的右半部分如果中间值大于目标值则目标值在数组的左半部分。二分查找解题的前提数组元素是有序且不重复的。因为一旦有重复元素二分查找返回的元素下标可能不是唯一的。所以只有当题目满足上述条件后才可以考虑是否使用二分法。二、二分法的边界条件二分法的区间定义一般分为两种左闭右闭即[left, right]左闭右开[left, right)三、二分法的写法1、左闭右闭[left, right]左闭右闭区间需要注意一下两点a、while (left right)要使用因为left right是有意义的b、if (nums[middle] target) right要赋值为middle - 1因为当前这个nums[middle]不一定是target那么接下来要查找的左区间结束下标位置就是middle - 1代码如下示例intsearch(int*nums,intnumsSize,inttarget){intleft0;intrightnumsSize-1;intmiddle0;while(leftright){middle(leftright)/2;if(nums[middle]target){rightmiddle-1;}elseif(nums[middle]target){leftmiddle1;}else{returnmiddle;}}return-1;//没有知道返回-1}2、左闭右开[left, right代码如下示例intsearch(int*nums,intnumsSize,inttarget){intleft0;intrightnumsSize;//定义target在左闭右开区间里面[left, rightintmiddle0;while(leftright){//left right时区间[left, right属于空集middle(leftright)/2;if(nums[middle]target){rightmiddle;}elseif(nums[middle]target){//target位于[left, right中保证集合在左闭右开性可等价与[middle 1, rightleftmiddle1;}else{returnmiddle;}}return-1;//没有知道返回-1}