一妇多、LintCode鏈接

http://www.lintcode.com/zh-cn/problem/first-position-of-target/

二僧著、問(wèn)題描述

給定一個(gè)排序的整數(shù)數(shù)組（升序）和一個(gè)要查找的整數(shù)target，用O(logn)的時(shí)間查找到target第一次出現(xiàn)的下標(biāo)（從0開(kāi)始）遭京，如果target不存在于數(shù)組中圃酵，返回-1。

三嘿歌、關(guān)鍵點(diǎn)分析

• 升序數(shù)組
• 數(shù)據(jù)量
• n0<=n1<=n2<=....掸掏，數(shù)據(jù)可能連續(xù)相等
• 第一次出現(xiàn)的下標(biāo)

四、解決思路（Java）

1.數(shù)據(jù)量不大宙帝，遞歸法和非遞歸法

遞歸法

 public int binarySearch(int[] nums, int fromIndex, int toIndex, int target) {
        if (nums == null || nums.length <= 0
             || fromIndex > toIndex || fromIndex < 0 || toIndex >= nums.length) {
            return -1;
        }

        int midIndex = (fromIndex + toIndex) >>> 1;
        int midValue = nums[midIndex];

        if (midValue < target) {
            return binarySearch(nums, midIndex + 1, toIndex, target);
        } else if (midValue > target) {
            return binarySearch(nums, fromIndex, midIndex - 1, target);
        } else {
            int beforeIndex = binarySearch(nums, fromIndex, midIndex - 1, target);
            return beforeIndex > 0 ? beforeIndex : midIndex;
        }
    }

非遞歸法

 public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }

        int resultIndex = -1;

        int fromIndex = 0;
        int toIndex = nums.length - 1;

        while (fromIndex <= toIndex) {
            int midIndex = (fromIndex + toIndex) >>> 1;
            int midValue = nums[midIndex];

            if (midValue < target) {
                fromIndex = midIndex + 1;
            } else if (midValue > target) {
                toIndex = midIndex - 1;
            } else {
                resultIndex = midIndex;
                toIndex = midIndex - 1;
            }
        }
        return resultIndex;
    }

2.數(shù)據(jù)量大丧凤，借助樹(shù)或堆和Quick Select算法（TODO）

五、相關(guān)

1.源碼中的二分查找

    SparseArray.get方法：
    public E get(int key, E valueIfKeyNotFound) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i];
        }
    }

    ContainerHelpers.binarySearch()方法：
    static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found //從這里可以看出只要找到就返回步脓，不考慮數(shù)據(jù)連續(xù)相等的情況
            }
        }
        return ~lo;  // value not present
    }

2.鏈接

維基-二分搜索