已排序的整数数组相关查找返回索引问题

对于数组的应用大家一定不会陌生，今天要介绍的就是两种有关数组中对于指定元素的查找问题.

1、给定一个排序的整数数组，找到给定目标值的起始位置和结束位置。

题目要求：

算法的运行时复杂度必须是O（log n）的顺序。如果在数组中找不到目标，返回[-1，-1 ]。

示例：

输入数组a[ ]={1,2,3,3,4,4,5}；target=3；返回结果{2，3}；

解题思路： （1）定义左右指针left和right：left=0；right=n-1； （2）当left小于right的时候，采用二分查找的方法查找指定数据，如果找到了就将left和right存起来，没找到就返回{-1，-1}；

代码实现：

vector<int> searchRange(int A[], int n, int target) { int left=0; int right=n-1; vector<int> res; res.push_back(-1); res.push_back(-1); while(left<=right) { //找到了就将下标存起来 if(A[left]==target&&A[right]==target) { res[0]=left; res[1]=right; break; } else {//二分查找遍历数组 int mid=left+((right-left)>>1); if(A[mid]<target) left=mid+1; else if(A[mid]>target) right=mid-1; else{ if(A[right]==target) ++left; else --right; } } } return res; }

2、给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。

示例： [1,3,5,6]，5 → 2 [1,3,5,6]，2 → 1 [1,3,5,6]， 7 → 4 [1,3,5,6]，0 → 0 解题思路： 遍历给定数组中的数直到找到不小于target的数为止，当前位置就是要返回的位置（如果与target相等符合题意就是该位置，如果大于target，那么该数字以及该数字之后的向后移一位并将target插入该位置） 代码实现： 这里采用二分查找的方法查找指定数据target，有利于降低时间复杂度

int searchInsert(int A[], int n, int target) { int left=0; int right=n-1; if(n==0) return 0; while(left<right)//查找元素 { int mid=left+((right-left)>>1); if(target<A[mid]) right=mid-1; else if(target>A[mid]) left=mid+1; else { return mid; } }//此时没有找到，就需要将要插入的元素与左元素比较 if(A[left]>=target) return left; else return left+1; }