Leetcode 二分查找 Search Insert Position - c++编程基础

Search Insert Position

Total Accepted: 14279 Total Submissions: 41575

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

题意：输出一个元素在一个已排序的数组中的位置，如果不存在输出它应该插入的位置
思路：二分查找，如果找到就输出位置，找不到就输出它应该插入的位置
复杂度：时间O(log n)，空间O(1)

相关题目：

Search for a Range

Search a 2D Matrix

class Solution {
public:
    
    
    int searchInsert(int A[], int n, int target) {
    	int s = 0, e = n - 1, m ; //中间数，偶数个的时候取前一个
    	while(s <= e){
    		m = (s + e) / 2;
    		if(A[m] == target) return m;
    		if(A[m] < target) s = m + 1;
    		if(A[m] > target) e = m - 1;
    	}
    	if(A[m] > target) return m;
    	else return m + 1;
    }
};