首页 > 试题广场 >

搜索插入位置

[编程题]搜索插入位置

热度指数：11119 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个有序的数组和一个目标值，如果数组中存在该目标值，则返回该目标值的下标。如果数组中不存在该目标值，则返回如果将该目标值插入这个数组应该插入的位置的下标
假设数组中没有重复项。
下面给出几个样例：
[10,30,50,60], 50 → 2
[10,30,50,60], 20 → 1
[10,30,50,60], 70 → 4
[10,30,50,60], 0 → 0

示例1

输入

[10,30,50,60],50

输出

算法知识视频讲解

Java

詆調壹點

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;
	}
}

发表于 2017-03-26 16:56:54 回复(0)

AlgorithmM

/**
从左到右，遇到第一个等于或大于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;
    }
};

发表于 2016-07-25 12:11:38 回复(0)

shijiacheng

/**
 * 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);
    }
}

发表于 2018-09-05 22:21:03 回复(0)

C/C++

kildallithro

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;
}

发表于 2020-02-08 20:42:52 回复(0)

Java

HW柯可

解法一：
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;
    }
}

编辑于 2019-06-26 10:30:26 回复(0)

页川先生

 int searchInsert(int A[], int n, int target) {
        int low=0;
        int high=n-1;
        int mid;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid]==target)
                return mid;
            else if(A[mid]<target)
                low=mid+1;
            else
                high=mid-1;
        }
        return low;
    }

发表于 2017-11-06 19:09:05 回复(0)

C/C++

nbgao

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int i=0;
        for(i=0;i<n;i++)
        {
        	if(target <= A[i])
        		return i;
		}
        return n; 
    }
};

发表于 2017-07-28 01:16:03 回复(0)

xiao_lai

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;
    }
};

发表于 2016-07-22 16:06:48 回复(1)

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  int searchInsert(int* A, int n, int target) {
    return lower_bound(A, A + n, target) - A;
  }
};

发表于 2021-09-27 10:43:25 回复(0)

Python 3

KG201908131728826

class Solution:
def searchInsert(self , A , target ):
# write code here
start = 0
end = len(A) - 1
key = -1
while(start<=end):
mid = (start+end) // 2
if A[mid] < target:
start = mid + 1
if key < mid:
key = mid
else:
end = mid - 1
return key + 1

编辑于 2021-07-26 22:42:08 回复(0)

ponmmains

import java.util.*;

public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public int searchInsert (int[] A, int target) {
// write code here
int i = 0, j = A.length - 1, mid;
while (i <= j) {
mid = (i + j) / 2;
if (A[mid] == target)
return mid;
else if (A[mid] > target)
j = mid - 1;
else
i = mid + 1;
}

return i;
}
}

发表于 2020-09-29 15:26:53 回复(0)

JavaScript

钱多事少离家近offer

/**
  * 
  * @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
};

发表于 2020-09-16 21:27:26 回复(0)

Java

日常不想上班的码农

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);
		}
	}
}

发表于 2020-08-01 11:18:39 回复(0)

JavaScript

陈运齐

function searchInsert( A ,  target ) {
    // write code here
    let ind = A.indexOf(target);
    if(ind !== -1) return ind;
    A.push(target);
    A.sort((a, b) => {return a - b;})
    return A.indexOf(target);
}

编辑于 2020-07-08 14:54:20 回复(0)

Python

黄沙遮天

垃圾题

class Solution:
    def searchInsert(self , A , target ):
        # write code here
        i=0
        flag=0
        for i in range(len(A)):
             if target<=A[i]:
                flag=1
                break
             else:
                continue
        if flag==1:
            return i
        else:
            return len(A)

发表于 2020-06-11 13:16:26 回复(0)

merlinssea

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;
    }
};

发表于 2020-04-29 22:02:07 回复(0)

FMAO

循环遍历数组，不管A[i]大于或是等于target，或者全都小于target，均直接返回i。

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        if(n==0)
            return 1;
        int i;
        for(i=0;i<n&&A[i]<target;i++);
        return i;
    }
};

发表于 2020-02-07 17:32:51 回复(0)

C/C++

ltaoj

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int moreIndex = -1;
        for (int i = 0;i < n;i++) {
            if (A[i] == target) {
                return i;
            }
            if (A[i] > target && moreIndex == -1) {
                moreIndex = i;
            }
        }
        return moreIndex != -1 ? moreIndex : n;
    }
};

发表于 2020-01-11 16:12:08 回复(0)

wuba

public class Solution {
    public int searchInsert(int[] A, int target) {
         int len = A.length;
        if(len == 0) return 0;
        for(int i=0; i<len; i++){
            if(A[i] >= target) return i;
            if(A[i]<target){
                continue;
            }
        }
        return len;
    }
}

编辑于 2019-11-13 11:58:07 回复(0)

C/C++

(:∇:)我太难了

class Solution {
public:
int searchInsert(int A[], int n, int target) {
    if (A == NULL || n <= 0)
        return -1;
    int i = 0;
    for (i = 0;i < n;i++) {
        if (A[i] == target)
            return i;
        else if (A[i] > target)
            return i;
    }
    return i;
}
};

发表于 2019-08-02 21:43:33 回复(0)