[算法学习]--二分查找

定义：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

基本解法：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;
        while (start <= end) {
            mid = (end + start) / 2;
            int midNums = nums[mid];
            if (target < midNums) {
                end = mid - 1;
            } else if (target > midNums) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        for (int i = 0;i < nums.length;i++) {
            if (target < nums[i]) {
                return i;
            }
        }
        return nums.length;
    }
}