详细见：leetcode.com/problems/search-insert-position
Java Solution: github
package leetcode; public class P035_SearchInsertPosition { public static void main(String[] args) { System.out.println(new Solution().searchInsert(new int[] {1,3,5,6}, 69)); } /* * 0 ms * 16.95% * 又是试错型AC，今天怎么了 */ static class Solution { public int searchInsert(int[] nums, int target) { if (nums == null || nums.length == 0) return 0; if (target > nums[nums.length - 1]) return nums.length; return getIndex(nums, 0, nums.length - 1, target); } private int getIndex(int[] nums, int sti, int eni, int target) { while (sti < eni) { int mid = (sti + eni) >> 1; // mid = (mid & 0x1) == 1 ? (mid >> 1) + 1 : mid >> 1; if (nums[mid] > target) eni = mid; else if (nums[mid] < target) sti = mid + 1; else return mid; } return sti; } } }C Solution: github
/* url: leetcode.com/problems/search-insert-position/ 3ms 23.90% */ int searchInsert(int* nums, int numsSize, int target) { //first equal or larger int i = 0, j = numsSize - 1, m = 0; if (numsSize == 0) return 0; if (nums[i] >= target) return i; if (nums[j] < target) return j + 1; while (i < j) { m = i + (j - i) / 2; if (nums[m] >= target) { j = m; } else { i = m + 1; } } return i; } int main() { int nums[] = {1,3,5,6}; int v[] = {5, 2, 7, 0}; int i = 0; int numsSize = 4; for (i = 0; i < numsSize; i ++) { printf("target is %d answer is %d \r\n", v[i], searchInsert(nums, numsSize, v[i])); } }Python Solution: github
#coding=utf-8 ''' url: leetcode.com/problems/search-insert-position/ @author: zxwtry @email: zxwtry@qq.com @date: 2017年4月4日 @details: Solution: 58ms 21.67% ''' class Solution(object): def searchInsert(self, n, t): """ :type n: List[int] :type t: int :rtype: int """ nn = 0 if n == None else len(n) if nn == 0: return 0 return self.binarySearchFirstEqualOrLarger(n, 0, nn, t) #[i, j) def binarySearchFirstEqualOrLarger(self, n, i, j, t): j -= 1 if n[j] < t: return j + 1 while i < j: m = (i + j) // 2 if n[m] >= t: j = m else: i = m + 1 return i
