binarySearch

Description

二分查找，是arrays里常考的习题。对于同一题型，有几种写法，有的是start < end，有的是start + 1 < end。判断和中间值大小比较之后，有的是start = mid，有的是start = mid + 1等。并没有一个同一的解法，这里先给出一个统一的解法。

Solution1

class Solution {
    //对于一个递增的序列，找到第一个符合的目标值
    public void binarySearch(int[] A, int target) {
        if (A.length == 1) {
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else if (A[mid] > target) {
                end = mid;
            }
        }
        if (A[start] == target) {
            return start;
        }
        if (A[end] == target) {
            return end;
        }
        return -1;
        }
}

Solution2

class Solution {
    //对于一个递增的序列，找到最后一个符合的目标值
    public void binarySearch(int[] A, int target) {
        if (A.length == 1) {
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                start = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else if (A[mid] > target) {
                end = mid;
            }
        }
        if (A[end] == target) {
            return end;
        }
        if (A[start] == target) {
            return start;
        }
        return -1;
        }
}

Analyse

二分查找，有几种写法。这里定一个标准的写法，首先while的条件是start和end相邻或者相交就退出。因为是要求先出现的值，循环里面如果A[mid] == target的话，end = mid退出。而退出之后可能出现start和end都是和target相等的情况，所以先判断start，如果A[start] == target，那么直接返回start，再判断end，否则就直接返回-1。这里不需要改变的时候是再给额外加上1或者减去1，而是直接替换，方便好写！

Tips

• 1.求mid的时候要写成mid = start + (end - start) / 2，这里是为了避免出现start + end直接超过maxint的大小，出现越界。
• 2.记住每次最后start和end都要比，看是要最先的值还是最后的值，然后进行返回判断。

Sample1

//二分查找的变形，找到有序数组的插入位置
public class Solution {
        //find the first position >= target
        public int searchInsert(int[] A, int target) {
            int start = 0, end = A.length - 1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (A[mid] == target) {
                    return mid;
                } else if (A[end] < target) {
                    start = mid;
                } else {
                    end = mid;
            }
            if (A[start] >= target) {
                return start;
            } else if (A[end] >= target) {
                return end;
            } else {
                return end + 1;
            }
        }
        }
    }

Analyse

在有序数组中找到插入的节点，那么就第一个大于等于target的位置，那么就插入到该位置上去。这里还是要判断start可能和end都存在的情况，所以start和end都得同时判断。

Sample2

//findMin，在旋转的有序数组里找到最小值
    public class Solution{
        public int findMin(int[] nums) {
            int start = 0, end = nums.length - 1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (nums[mid] >= nums[end]) {
                    start = mid;

                } else {
                    end = mid;
                }
    
            }
        if (nums[start] < nums[end]) {
            return nums[start];
        } else {
            return nums[end];
        }
        }
     }

Analyse

这里查找有序数组的最小值，通过这个有序循环可以得到结果。