在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1
样例 给出数组 [1, 2, 2, 4, 5, 5].
对于 target = 2, 返回 1 或者 2. 对于 target = 5, 返回 4 或者 5. 对于 target = 6, 返回 -1.
//最基础的二分查找算法#include <stdio.h>#include <vector>#include <iostream>using namespace std;class Solution {public: /** * @param A an integer array sorted in ascending order * @param target an integer * @return an integer */ int findPosition(vector<int>& A, int target) { // Write your code here int n = A.size(); if(n==0){ return -1; } int start=0; int end=n-1; while(start+1 < end){ int mid = start+(end-start)/2; if(A[mid] == target){ return mid; }else if(A[mid] < target){ start = mid; }else{ end = mid; } } if(A[start] == target){ return start; } if(A[end] == target){ return end; } return -1; }};给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target 第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。 样例 在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。
加了一段往前搜索第一次出现的代码。。。好像不太优雅
#include <stdio.h>#include <vector>#include <iostream>using namespace std;class Solution {public: /** * @param nums: The integer array. * @param target: Target number to find. * @return: The first position of target. Position starts from 0. */ int binarySearch(vector<int> &array, int target) { // write your code here int n = array.size(); if(n==0){ return -1; } int start=0; int end=n-1; while(start+1 < end){ int mid = start+(end-start)/2; if(array[mid] == target){ while(array[mid] == array[mid-1]){ mid--; } return mid; }else if(array[mid] < target){ start = mid; }else{ end = mid; } } if(array[start] == target){ return start; } if(array[end] == target){ return end; } return -1; }};新闻热点
疑难解答
