1. 搜索旋转数组（33）
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
（class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n==0) return -1; if (n==1){ return nums[0]==target?0 :-1; } int l = 0,r = n-1; while(l<=r){ int mid = (l+r)/2; if (nums[mid]==target) return mid; if (nums[0]<=nums[mid]){ if (nums[mid]>target && nums[0] <=target){ r =mid-1; }else{ l = mid+1; } }else { if (nums[mid]<target&& nums[n-1]>=target){ l =mid+1; }else{ r= mid-1; } } } return -1; } }
2. 在排序数组中查找元素的第一个和最后一个位置(34)
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
class Solution { public int[] searchRange(int[] nums, int target) { int n = nums.length; if (n==0) return new int[]{-1,-1}; if (n==1) return nums[0]==target? new int[]{0,0}: new int[]{-1,-1}; int l = 0,r = n-1; while(l<=r){ int mid = (l+r)/2; if (nums[mid]==target){ int first = mid; int end = mid; while(first>=l && nums[first]==nums[mid]){ first--; } while(end<=r && nums[end]==nums[mid]){ end++; } return new int[]{first+1,end-1}; }else if (nums[mid]>target){ r= mid-1; }else{ l= mid+1; } } return new int[]{-1,-1}; } }
3. 搜索插入位置（35）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
class Solution { public int searchInsert(int[] nums, int target) { int n =nums.length; int l =0, r =n-1; while(l<=r){ int mid = (l+r)/2; if (nums[mid]==target) return mid; if (nums[mid]>target){ r= mid-1; }else{ l =mid+1; } } return l; } }