search insert position@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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

» Solve this problem

	class Solution {
	public:
	int findIndex(int* a, int begin, int end, int target)
	{
	if(a==NULL) return 0;
	if(begin==end)
	{
	if(target<a[begin]) return begin;
	if(target>a[end]) return end+1;
	}
	int mid=(begin+end)/2;
	if(a[mid]>target)
	findIndex(a, begin, mid, target);
	else if(a[mid]<target)
	findIndex(a, mid+1, end, target);
	else
	return mid;
	}
	int searchInsert(int A[], int n, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	return findIndex(A, 0, n-1, target);
	}
	};

view raw search insert position hosted with ❤ by GitHub

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

view raw search insert positionclass Solution { public: int searchInsert(int A[], int n, int target) { for(int i=0; i<n; i++){ if(A[i]==target) return i; if(A[i]>target) return i; } return n; } }; hosted with ❤ by GitHub