int search(int[] a, int key) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (a[mid] == key) return mid; // key found

            if (a[mid] < key) lo = mid + 1;
            else hi = mid - 1;
        }

        return -(lo + 1); // key not found, position to be inserted is returned
    }
This is binary search algorithm, Time complexity is O(lgN) and does use extra space.
This finds any occurrence of given key
src/algo/sortingandsearching/BinarySearch.java