关于二分算法

1、常规二分

功能：有序数组中查找某个元素的位置。

int dichotomy_default(int[] A, final int target) {
        int result = -1;
        if (null == A || A.length == 0) {
            return result;
        }
        int left = 0, right = A.length - 1;
        while (left <= right) {
            final int mid = (left + right) / 2;
            if (target == A[mid]) {
                result = mid;
                break;
            } else if (target < A[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

---

2、二分拓展之一

有序数组中存在重复数值，找到某个数值在数组中出现的第一个或者最后一个位置。算法的核心是：在找到某个位置对应的数值与目标值相等时，判断是否继续向左或者向右移动。

int dichotomy_low(int[] A, final int target) {
        int result = -1;
        if (null == A || A.length == 0) {
            return result;
        }
        int left = 0, right = A.length - 1;
        while (left <= right) {
            final int mid = (left + right) / 2;
            if (target == A[mid]) {
                if ((mid > 0 && target != A[mid - 1]) || mid == 0) {
                    result = mid;
                    break;
                } else {
                    right = mid - 1;
                }
            } else if (target < A[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

---

int dichotomy_high(int[] A, final int target) {
        int result = -1;
        if (null == A || A.length == 0) {
            return result;
        }
        int left = 0, right = A.length - 1;
        while (left <= right) {
            final int mid = (left + right) / 2;
            if (target == A[mid]) {
                if ((mid < right && target != A[mid + 1]) || mid == right) {
                    result = mid;
                    break;
                } else {
                    left = mid + 1;
                }
            } else if (target < A[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

3、二分拓展之二

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
算法的核心是：不论什么情况，总能在[left mid]和[mid right]两个区间中找到一个是单调的，这样就容易判断目标值在哪个区间，并且做出调整。

int dichotomy_hard(int[] A, final int target) {
        int result = -1;
        if (null == A || A.length == 0) {
            return result;
        }
        int left = 0, right = A.length - 1;
        while (left <= right) {
            final int mid = (left + right) / 2;
            if (target == A[mid]) {
                result = mid;
                break;
            } else if (A[left] <= A[mid]) {
                if (target >= A[left] && target < A[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > A[mid] && target <= A[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return result;
    }

---

4、二分拓展之三

拓展二的情况是数组中没有重复的数值出现，如果有重复的数值出现呢？其实在这种情况下，判断A[left] <= A[mid]的时候，相等的情况要单独去判断，如果相等只要left++即可。

int dichotomy_duplicate(int[] A, final int target) {
        int result = -1;
        if(null == A || A.length == 0) {
            return result;
        }
        int left = 0, right = A.length -1;
        while(left <= right) {
            final int mid = (left + right) / 2;
            if(target == A[mid]) {
                result = mid;
                break;
            }
            if(A[left] < A[mid]) {
                if(A[left] <= target && target < A[mid]) {
                    right = mid -1;
                } else {
                    left = mid + 1;
                }
            } else if(A[left] > A[mid]) {
                if(A[mid] < target && target <= A[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                left++;
            }
        }
        return result;
    }