本文共 9078 字，大约阅读时间需要 30 分钟。
https://leetcode-cn.com/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2 示例 2:输入: [1,3,5,6], 2
输出: 1 示例 3:输入: [1,3,5,6], 7
输出: 4 示例 4:输入: [1,3,5,6], 0
输出: 0直接在区间[0, nums.length - 1] 二分查找，直到找到了相等的元素直接返回位置，或者没找到，此时start > end。
start > end时上一轮肯定是start==end，此时分析如下：
综上，这里只需要直接返回start就是没找到该数时应该放入的位置。
class Solution { public int searchInsert(int[] nums, int target) { if (nums == null){ return -1; } return find(nums, target, 0, nums.length - 1); } private int find(int[] nums, int target, int start, int end){ if(start > end){ // 这种情况，上一轮肯定是start==end // 如果是target < nums[mid]，则end=mid-1，也就是说target比mid数小，应该放在start处，而mid数右移 // 如果是target > nums[mid]，则start=mid + 1，也就是说target比mid数大，应该放在原start右边一位 // 综上，这里只需要直接返回start就是没找到该数时应该放入的位置 return start; } int mid = (start + end) / 2; if(target == nums[mid]){ // 如果找到了就返回该位置 return mid; }else if(target < nums[mid]){ return find(nums, target, start, mid - 1); }else{ return find(nums, target, mid + 1, end); } }} O(logN)
O(logN)
代码如下：
class Solution { public int searchInsert(int[] nums, int target) { if(nums == null || nums.length == 0){ return -1; } int start = 0; int end = nums.length - 1; int mid; while(start <= end){ mid = (start + end) /2; if(target == nums[mid]){ return mid; }else if(target < nums[mid]){ end = mid - 1; }else{ start = mid + 1; } } return start; }} https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4] 示例 2:输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]直接在区间[0, nums.length - 1] 二分查找，直到start > end或找到了相等元素：
-1, -1最坏情况，可能元素全部相等，此时时间复杂度为O(N)
class Solution { private int[] result = { -1, -1}; public int[] searchRange(int[] nums, int target) { if(nums == null || nums.length == 0){ return result; } return search(nums, target, 0, nums.length - 1); } private int[] search(int[] nums, int target, int start, int end){ if(start > end){ return result; } int mid = (start + end) / 2; if (nums[mid] == target){ result[0] = mid; result[1] = mid; for(int i = mid - 1; i >=0; i--){ if(nums[i] < target){ break; }else{ result[0] = i; } } for(int i = mid + 1; i < nums.length; i++){ if(nums[i] > target){ break; }else{ result[1] = i; } } return result; }else if (nums[mid] < target){ return search(nums, target, mid + 1, end); }else { return search(nums, target, start, mid - 1); } }} 最坏情况O(N)
最坏情况O(N)
2.3方法最坏情况，可能元素全部相等，此时时间复杂度为O(N)。
题目要求时间复杂度O(logN)，也就是说左右边界也必须通过二分查找实现。
class Solution { private int[] result = { -1, -1}; public int[] searchRange(int[] nums, int target) { if(nums == null || nums.length == 0){ return result; } int start = 0; int end = nums.length - 1; int mid = 0; int targetIndex = -1; while(start <= end){ mid = (start + end) /2; if(target == nums[mid]){ targetIndex = mid; break; }else if(target < nums[mid]){ end = mid - 1; }else{ start = mid + 1; } } int left = -1; int right = -1; if(targetIndex > -1){ // 此时说明找到了一个相等的 left = targetIndex; right = targetIndex; // 继续查找左边界 start = 0; end = mid - 1; while(start <= end){ int mid2 = (start + end) / 2; if(target == nums[mid2]){ left = mid2; end = mid2 - 1; }else if(target < nums[mid2]){ end = mid2 - 1; }else{ start = mid2 + 1; } } // 查找右边界 start = mid + 1; end = nums.length - 1; while(start <= end){ mid = (start + end) / 2; if(target == nums[mid]){ right = mid; start = mid + 1; }else if(target < nums[mid]){ end = mid - 1; }else{ start = mid + 1; } } result[0] = left; result[1] = right; } return result; }} O(logN)
O(1)
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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二分搜索，如果mid就是目标就直接返回，否则：
target < nums[mid]
还需要判断target是否大于等于nums[start]：target > nums[mid]
还需要判断target是否小于等于nums[end]：这样虽然能找到目标元素，但问题在于最坏情况时间复杂度为O(N)
class Solution { public int search(int[] nums, int target) { int result = -1; if(nums == null || nums.length == 0){ return result; } int start = 0; int end = nums.length - 1; int mid; while (start <= end) { mid = (start + end) / 2; if (nums[mid] == target) { result = mid; break; } if (target < nums[mid]){ // target 在mid左边 if(target >= nums[start]){ // 这表明start->mid有序，且target位于其间，只需要减小右边界 end = mid - 1; }else{ // 要么start->mid无序，此时只能把nums[start]排除掉 start++; } }else{ if(target <= nums[end]){ // 这表明mid->end有序，且target位于其间，只需要增长左边界 start = mid + 1; }else{ // 要么mid->end无序，此时只能把nums[end]排除掉 end--; } } } return result; }} 最坏情况O(N)
O(1)
前面算法最坏情况时间复杂度为O(N)，因为我们无法在某些情况判断到底应该将边界移动到哪儿，只能一个一个移动。
我们重新考虑，仍然二分搜索，如果mid就是目标就直接返回，否则：
nums[start] <= nums[mid]
此时[start, mid]有序，还需要判断target是否处于[start, mid]中：否则nums[mid] < nums[start]
此时[mid, end]有序，还需要判断target是否处于[mid, end]中：可以看到，我们现在首先关注的不再是target而是mid，每次都找到mid所在的有序区间，然后再判断target。
class Solution { public int search(int[] nums, int target) { int result = -1; if(nums == null || nums.length == 0){ return result; } int start = 0; int end = nums.length - 1; int mid; while (start <= end) { mid = (start + end) / 2; if (nums[mid] == target) { result = mid; break; } if (nums[start] <= nums[mid]) { if (nums[start] <= target && target < nums[mid]) { end = mid - 1; } else { start = mid + 1; } } else { if(nums[mid] < target && target <= nums[end]) { start = mid + 1; }else{ end = mid - 1; } } } return result; }} O(logN)
O(1)
转载地址：http://qlpkb.baihongyu.com/