vlambda博客
学习文章列表

题目：

    给定一个n个元素有序的（升序）整形数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。

难易程度：简单

使用语言：Java

示例：

    输入：nums = [1,2,3,4,5,6,7],target = 6;

    输出：5

提示：

    1.你可以假设nums中的所有元素是不重复的。

    2.n将在[1,10000]之间。

    3.nums的每个元素都将在[-9999,9999]之间。

解题：

    二分查找是一种基于比较目标值和中间元素的教科书式算法。

    1）如果目标值等于中间元素，则找到目标值。

    2）如果目标值较小，继续在左侧搜索。

    3）如果目标值较大，则继续在右侧搜索。

复杂度分析：

    时间复杂度：O（logN）；

    空间复杂度：O（1）。

代码实现：

class Solution {
    public int search(int[] nums, int target) {
        int minIndex = 0;   //最小索引
        int maxIndex = nums.length - 1; //最大索引
        int midIndex;
        while (minIndex <= maxIndex) {
            midIndex = (minIndex + maxIndex) / 2;
            if (nums[midIndex] == target) {
                System.out.println(midIndex);
                return midIndex;
            }
            if (nums[midIndex] < target) {
                minIndex = midIndex + 1;
            } else {
                maxIndex = midIndex - 1;
            }
        }
        System.out.println("查找的元素不存在~~");
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int target = 6;
        Solution s = new Solution();
        s.search(nums, target);
    }
}