LeetCode && 剑指offer 经典题目总结——查找

1.搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解法：

找到旋转的下标 rotation_index ，也就是数组中最小的元素。二分查找在这里可以派上用场。
在选中的数组区域中再次使用二分查找。

public int search(int[] nums, int target) { if(nums.length == 0) return -1; if(nums.length == 1){ return nums[0] == target ? 0:-1; } int rotate_index = find_rotate_index(nums,0,nums.length-1); if(nums[rotate_index] == target){ return rotate_index; } if(rotate_index == 0){ return binarySearch(nums,0,nums.length-1,target); } if(nums[0] > target){ return binarySearch(nums,rotate_index,nums.length-1,target); } return binarySearch(nums,0,rotate_index-1,target); } public int find_rotate_index(int[] nums,int lo, int hi) { //没有旋转 if(nums[lo] < nums[hi]){ return 0; } while(lo <= hi){ int mid=(lo+hi)/2; if(nums[mid+1] < nums[mid]){ return mid+1; }else{ if(nums[mid] < nums[lo]){ hi = mid-1; }else{ lo = mid+1; } } } return 0; } //二分查找 public int binarySearch(int[] nums,int lo, int hi,int target) { while(lo <= hi){ int mid=(lo+hi)/2; if(nums[mid] == target){ return mid; }else if(nums[mid] > target){ hi = mid-1; }else { lo = mid+1; } } return -1; }

2.搜索旋转排序数组 II

上题的延伸题，本题中的 nums 可能包含重复元素。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

解法：
与上题的区别是在寻找旋转下标时，如果是在重复元素处旋转的，那么只能遍历寻找。

class Solution { public boolean search(int[] nums, int target) { if(nums.length == 0) return false; if(nums.length == 1){ return nums[0] == target ? true:false; } int rotate_index = find_rotate_index(nums,0,nums.length-1); if(nums[rotate_index] == target){ return true; } if(rotate_index == 0){ return binarySearch(nums,0,nums.length-1,target); } if(nums[0] > target){ return binarySearch(nums,rotate_index,nums.length-1,target); } return binarySearch(nums,0,rotate_index-1,target); } public int find_rotate_index(int[] nums,int lo, int hi) { //没有旋转 if(nums[lo] < nums[hi]){ return 0; } while(lo <= hi){ int mid=(lo+hi)/2; //在重复元素处旋转的情况下，遍历处理 if(nums[mid] == nums[lo] && nums[mid] == nums[hi]){ for(int i = 1;i < nums.length;i++){ if(nums[i] < nums[i-1]){ return i; } } return 0; } if(nums[mid+1] < nums[mid]){ return mid+1; }else{ if(nums[mid] < nums[lo]){ hi = mid-1; }else{ lo = mid+1; } } } return 0; } //二分查找 public boolean binarySearch(int[] nums,int lo, int hi,int target) { while(lo <= hi){ int mid=(lo+hi)/2; if(nums[mid] == target){ return true; }else if(nums[mid] > target){ hi = mid-1; }else { lo = mid+1; } } return false; } }