题目描述

题目1

题目2

解题思路

两道题都可以使用折半查找（二分查找）的思路，找出目标位置。题目1直接返回目标target的数组下标；题目2使用二分查找逐渐逼近第一个大于等于目标target的数组下标并返回。

二分查找：

• 若target等于中间元素，直接返回中间元素下标；
• 若target小于中间元素，向左侧查找（left, mid）;
• 若target大于中间元素，向右侧查找（mid, right）;

代码实现

题目1

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = 0;
        
        while(left <= right){
            mid = left + (right - left) / 2;    //取中间下标
            if(nums[mid] == target) return mid;
            if(nums[mid] < target) left = mid + 1;    //向右侧查找
            if(nums[mid] > target) right = mid - 1;    //向左侧查找
        }

        return -1;
    }
}

题目2

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1,mid = 0;
        while(left<=right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] < target) left = mid + 1;
            if(nums[mid] > target) right = mid - 1;
        }

        return left;
    }
}