给出一个有序的数组和一个目标值,如果数组中存在该目标值,则返回该目标值的下标。如果数组中不存在该目标值,则返回如果将该目标值插入这个数组应该插入的位置的下标
假设数组中没有重复项。
下面给出几个样例:
[10,30,50,60], 50 → 2
[10,30,50,60], 20 → 1
[10,30,50,60], 70 → 4
[10,30,50,60], 0 → 0
[10,30,50,60],50
2
public class Solution { public int searchInsert(int[] A, int target) { // 二分查找 int low = 0; int high = A.length - 1; while (low <= high) { int mid = (low + high) / 2; if(A[mid] == target) return mid; else if(A[mid] < target) low = mid + 1; else high = mid - 1; } // 没找到返回low,即插入位置 return low; } }
/**
从左到右,遇到第一个等于或大于target的元素,返回该元素的index,
对于大于target的元素的index就是应该插入元素的index,
如果没有符合上述条件的元素,则将target放在最后,即返回n
***/ class Solution {
public:
int searchInsert(int A[], int n, int target) {
for(int i =0 ; i < n; i++){
if (A[i]==target){
return i;
}
else if(A[i]>target){
return i;
}
}
return n;
}
};
/**
* 35. 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:
* <p>
* 输入: [1,3,5,6], 0
* 输出: 0
*
* @author shijiacheng
*/
public class Solution {
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length ==0 || target<=nums[0]){
return 0;
}
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target){
index = i;
break;
}
if (nums[i] < target){
index = i+1;
}
if (index > nums.length-1){
index = nums.length;
break;
}
}
return index;
}
public static void main(String[] args){
Solution s = new Solution();
int[] nums = {1,3};
int index = s.searchInsert(nums,5);
System.out.println(index);
}
}
int searchInsert(int A[], int n, int target) { int k=0,sub; while(A[k]!=target && k<n){ //暴力法找目标值位置 k++; } if(k<n) sub=k; else { //若目标值不在其中,找出其应插入的下标位置 int cnt=0; while(target>A[cnt] && cnt<n) cnt++; sub=cnt; } return sub; }
解法一: public class Solution { public int searchInsert(int[] A, int target) { //循环遍历数组,若目标数target小于等于A[i],则返回下标i,若循环能走完,则目标数target比数组最后一个数还要大,直接返回len+1 int len= A.length; for(int i = 0; i < len; i++){ if(A[i] >= target){ return i; } } return len; } } 解法二: public class Solution { public int searchInsert(int[] A, int target) { //二分法查找 int low = 0; int high = A.length - 1; while(low <= high){ int mid = (low + high)/2; if(A[mid] == target) return mid; else if(A[mid] < target) low = mid + 1; else high = mid - 1; } return low; } }
class Solution { public: int searchInsert(int A[], int n, int target) { //You may assume no duplicates in the array. //本题考查二分查找 if(n==0)return 0; int l=0,h=n,m; while(l<h){ m = l+((h-l)>>1); if(A[m]>target){ h=m; }else if(A[m]<target){ l=m+1; }else{ //找到了 return m; } } //没有找到 if(target<A[0]) return 0; if(target>A[n-1])return n; return h; } };
class Solution { public: int searchInsert(int* A, int n, int target) { return lower_bound(A, A + n, target) - A; } };
/** * * @param A int整型一维数组 * @param target int整型 * @return int整型 */ function searchInsert( A , target ) { // write code here let ind = A.indexOf(target); if(ind >= 0){ return ind; }else{ A.push(target); A.sort((a,b) => a-b); return A.indexOf(target); } } module.exports = { searchInsert : searchInsert };
import java.util.*; public class Solution { int index = -1; /** * * @param A int整型一维数组 * @param target int整型 * @return int整型 */ public int searchInsert (int[] nums, int target) { // write code here searchHelper(nums, 0, nums.length - 1, target); return index; } public void searchHelper(int[] nums, int left, int right, int target) { if (left > right) { // 如果没有该元素,则返回left的值(自己画一下就知道了) index = left; return; } int mid = (right - left) / 2 + left; if (nums[mid] == target) { index = mid; return; } else if (nums[mid] < target) { searchHelper(nums, mid + 1, right, target); } else { searchHelper(nums, left, mid - 1, target); } } }
class Solution { public: int searchInsert(int A[], int n, int target) { if(n==0) return 0; int i=0; while(i<n){ if(A[i]==target || A[i]>target) return i; i++; } return n; } };