👉前言👈
相信大家之前已经过学习二分查找算法了,也知道二分查找算法使用的前提:严格有序的数组。那是不是永远都需要满足这个前提才能使用二分查找算法呢?本文将给出一些二分查找算法类型的题目,与你一探究竟。
👉二分查找👈
给定一个 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
提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
以上就是二分查找的母体了,这是最简单、最基础的。现在我们来写代码实现它。
int search(int* nums, int numsSize, int target) { int left = 0; int right = numsSize - 1; while (left <= right) { int mid = left + (right - right) / 2; if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else return mid; } return -1; }
分析:二分查找算法有左闭右闭区间和左闭右开区间两种写法,博主的二分查找算法的写法均采取的左闭右闭区间的写法。采用左闭右闭区间写法时,当 nums[mid] > target 时,right = mid - 1;当 nums[mid] < target 时,left = mid + 1;当nums[mid] == target 时,直接 return mid。还需要注意的是 mid 要定义在 while 循环内部。
👉猜数字大小👈
猜数字游戏的规则如下:
- 每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
- 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):
-1:我选出的数字比你猜的数字小 pick < num
1:我选出的数字比你猜的数字大 pick > num
0:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num
示例 1:
输入:n = 10, pick = 6
输出:6
示例 2:
输入:n = 1, pick = 1
输出:1
提示:
1 <= n <= 2^31 - 1
1 <= pick <= n
int guessNumber(int n){ int left=1; int right=n; int mid=0; while(left<=right) { mid=left+(right-left)/2; if(guess(mid)==1) { left=mid+1; } else if(guess(mid)==-1) { right=mid-1; } else return mid; } return mid; }
分析:本题最需要注意的就是,接口函数 guess 返回值的意思,其他的写法都是按照二分查找算法的思路写就行了。
👉搜索插入位置👈
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104
int searchInsert(int* nums, int numsSize, int target) { int left = 0; int right = numsSize - 1; if (nums[right] < target) return numsSize; if (nums[0] > target) return 0; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else return mid; } return left; }
分析:当数组 nums 的最后一个元素小于 target 时,那么插入位置就是 numsSize;当数组 nums 的第一个元素大于 target 时,那么插入位置就是0。如果不符合上面两种情况的话,就会进入 while 循环。如果数组 nums 中包含了 target,那么二分查找就会找到其下标 mid,也就是插入位置,将插入位置 return 就行了。如果数组 nums 不包含 target,那么 left 迟早会大于 right 退出 while 循环,此时 left 就是插入位置,将其 return 就行了。
👉山脉数组的峰顶索引👈
符合下列属性的数组 arr 称为 山脉数组 :
arr.length >= 3
存在 i(0 < i < arr.length - 1)使得:
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ,返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
示例 1:
输入:arr = [0,1,0]
输出:1
示例 2:
输入:arr = [0,2,1,0]
输出:1
提示:
3 <= arr.length <= 104
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组
int peakIndexInMountainArray(int* arr, int arrSize) { int left = 1, right = arrSize - 2; int mid = 0; while (left <= right) { mid = left + (right - left) / 2; if (arr[mid] < arr[mid + 1]) { left = mid + 1; } else if (arr[mid] < arr[mid - 1]) { right = mid - 1; } else return mid; } return mid; }
分析:该题的二分查找算法和上面的题差不多,当时唯一不同的就是 left 的起始位置是0,right 的起始位置是 numsSize - 1
,这样初始化的目的是避免数组越界访问。
👉有效的完全平方数👈
给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
进阶:不要 使用任何内置的库函数,如 sqrt 。
示例 1:
输入:num = 16
输出:true
示例 2:
输入:num = 14
输出:false
提示:
1 <= num <= 2^31 - 1
bool isPerfectSquare(int num){ int left=0; int right=num; while(left<=right) { int mid=left+(right-left)/2; long square=(long)mid*mid; //将mid*mid强制类型转换为long,防止溢出 if(square>num) { right=mid-1; } else if(square<num) { left=mid+1; } else return true; } return false; }
分析:当不满足循环条件时,说明1到 num 之间没有任何一个数的平方等于 num,所以 return false
。
👉x 的平方根👈
给你一个非负整数 x ,计算并返回 x 的算术平方根 。
由于返回类型是整数,结果只保留整数部分 ,小数部分将被舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
int mySqrt(int x) { int left = 0; int right = x; while (left <= right) { int mid = left + (right - left) / 2; long n = (long)mid * mid; //强制类型转换,防止溢出 if (n > x) { right = mid - 1; } else if (n < x) { left = mid + 1; } else return mid; } return right; }
分析: 因为退出循环是 left > right
,而 left * left
是大于 x
的,right * right
是小于 x
的,所以return right
。
👉寻找比目标字母大的最小字母👈
给你一个排序后的字符列表 letters ,列表中只包含小写英文字母。另给出一个目标字母 target,请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时,字母是依序循环出现的。举个例子:
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’],则答案返回 ‘a’
示例 1:
输入: letters = ["c", "f", "j"],target = "a"
输出: "c"
示例 2:
输入: letters = ["c","f","j"], target = "c"
输出: "f"
提示:
2 <= letters.length <= 104
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters最少包含两个不同的字母
target 是一个小写字母
char nextGreatestLetter(char* letters, int lettersSize, char target) { if(target>=letters[lettersSize-1]) return letters[0]; int left=0; int right=lettersSize-1; while(left<=right) { int mid=left+(right-left)/2; if(letters[mid]>target) { right=mid-1; } else { left=mid+1; } } return letters[left]; }
👉寻找旋转排序数组中的最小值 II👈
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组
nums =[0,1,4,4,5,6,7]
在变化后可能得到:若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次,则可以得到 [0,1,4,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
示例 1:
输入:nums = [1,3,5]
输出:1
示例 2:
输入:nums = [2,2,2,0,1]
输出:0
提示:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转
思路:因为 nums 数组是经有序数组旋转得来的,所以 nums 数组左边的元素一定大于右边的元素(除旋转 n 次)。那么旋转数组的最小值肯定是在 nums 数组的右边,所以我们将 nums[mid] 和 nums[right] 进行比较。因为可能有重复的元素,所以存在三种比较结果。
nums[mid] > nums[right]时,left = mid + 1,去除掉不是最小的数字
nums[mid] = nums[right]时,right--,去除掉重复的数字或逼近循环条件
nums[mid] < nums[right]时,right = mid,保留目前最小的数字
循环结束,nums[left] 就是旋转数组的最小数字
int findMin(int* numbers, int numbersSize) { int left = 0; int right = numbersSize-1; while(left<=right) { int mid=left+(right-left)/2; if(numbers[mid]>numbers[right]) { left=mid+1; } else if(numbers[mid]<numbers[right]) { right=mid; } else { right--; } } return numbers[left]; }
分析:这道题的解法也适用于《寻找旋转排序数组中的最小值 I》,因为这个解法考虑的情况更加的全面,包含《寻找旋转排序数组中的最小值 I》中的所有情况。
👉总结👈
以上就是二分查找算法的全部内容了,如果大家觉得有收获的话,可以点个三连支持一下!谢谢大家啦!!!💖💝❣️