Leetcode 二分查找 Search Insert Position

 

 

 

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