leetcode-704. 二分查找

JAVA解法

class Solution {
    public int search(int[] nums, int target) {
        // 左右两个边界
        int left = 0, right = nums.length - 1;
        // 左边界小于等于右边界
        while (left <= right) {
            // 左右边界相加除以二加上左边界求中点防止溢出
            int mid = (right - left) / 2 + left;
            // 取出中点值
            int num = nums[mid];
            // 中点值为目标值即返回，大于目标值即右边界缩小，反之左边界扩大
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 找不到返回 -1
        return -1;
    }
}

题解分析

这道题用的是二分查找法。先获取两个边界的索引，当满足左边界小于等于右边界时，取中点与目标值对比，中点值为目标值即返回，大于目标值即右边界缩小，反之左边界扩大，直到找到目标值返回，找不到则返回 -1.

leetcode原题： 704. 二分查找