面试题 08.03. 魔术索引
解题思路
文章来源地址https://www.toymoban.com/news/detail-544065.html
- 改写递归二分查找的思路
- 首先查找mid的值是不是mid 如果是 由于有多个解,那么递归搜索左半边的空间
- 然后如果没找到,首先搜索左半边的空间,然后搜索右半边的空间
class Solution {
public int res = -1;
private void search(int[] nums,int low,int high){
if(low > high){
return;
}
int mid = low + (high - low) / 2;
// 如果找到 直接搜索左半边的空间
if(nums[mid] == mid){
res = mid;// 保存一下结果
search(nums,low,mid - 1);// 搜索左半边的空间
}
else{
// 如果没有找到 先搜索左半边 然后搜索右半边
search(nums,low,mid - 1);
if(res == -1 || res > high){
// 搜索右半边
search(nums,mid + 1,high);
}
}
}
// 递归二分查找
public int findMagicIndex(int[] nums) {
search(nums,0,nums.length - 1);
return res;
}
}
文章来源:https://www.toymoban.com/news/detail-544065.html
到了这里,关于【二分查找】面试题 08.03. 魔术索引的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!