Classical Binary Search

Description

Find any position of a target number in a sorted array. Return -1 if target does not exist.

Example

Given[1, 2, 2, 4, 5, 5].

For target =2, return 1 or 2.

For target =5, return 4 or 5.

For target =6, return -1.

Challenge

O(logn) time

Related problems

Closest Number in Sorted Array

Easy Last Position of Target

Easy First Position of Target

Implementation

Link: http://lintcode.com/en/problem/classical-binary-search/

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
        if(A.size() == 0) return -1;

        int start = 0, end = A.size() - 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;
    }
};