35.搜索插入位置
题目
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出:
代码(暴力遍历)
class Solution {
public int searchInsert(int[] nums, int target) {
for(int i = 0; i < nums.length; i++){
if(nums[i] >= target){
return i; //在数组最前面or直接找到or在某个数后面插入
}
}
return nums.length; //target最大,插入数组后面
}
}
代码(二分查找标准版)
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while(left <= right){
mid = left + (right - left)/2;
if(target < nums[mid]){
right = mid - 1;
}
else if(target > nums[mid]){
left = mid + 1;
}
else{
return mid;
}
}
return right + 1; //right指向待插入元素的前一个索引位置
}
}
代码(二分查找自己写的)
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
int index = -1; //返回结果,必须要初始化,-1可以改成别的数
while(left <= right){
//特殊情况1:target在最前面插入
if(target < nums[left]){
index = left; //插在最小值left位置
break;
}
//特殊情况2:target在最后面插入
if(target > nums[right]){
index = right + 1; //插在最大值right后面位置,不要忘+1
break;
}
//二分查找逻辑
mid = left + (right - left) / 2;
if(target < nums[mid]){
right = mid - 1;
}
else if(target > nums[mid]){
left = mid + 1;
}
else{
index = mid; //找到了查找元素
break;
}
}
return index;
}
}
34.在排序数组中查找元素的第一个位置和最后一个位置
题目
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10]
, target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10]
, target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0 输出:[-1,-1]
代码(两个二分查找)
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = getleft(nums,target);
int end = getright(nums,target);
//target在数组的最前面和最后面
if(start == -2 || end == -2){
return new int[]{-1,-1};
}
//有target这个数,长度大于1,返回找到的区间
if(end - start > 1){
return new int[]{start+1,end-1};
}
//target在数组区间内,但找不到,长度小于等于1
else{
return new int[]{-1,-1};
}
}
public int getleft(int[] nums,int target){
int left = 0;
int right = nums.length - 1;
int mid;
int start = -2; //左边界
while(left <= right){
mid = left + (right - left) / 2;
if(target > nums[mid]){
left = mid + 1;
}
else if(target <= nums[mid]){
right = mid -1;
start = right;
}
}
return start;
}
public int getright(int[] nums,int target){
int left = 0;
int right = nums.length - 1;
int mid;
int end = -2; //右边界
while(left <= right){
mid = left + (right - left) / 2;
if(target < nums[mid]){
right = mid - 1;
}
else if(target >= nums[mid]){
left = mid + 1;
end = left;
}
}
return end;
}
}