【LeeCode】704. 二分查找

【题目描述】

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

​​​​https://leetcode.cn/problems/binary-search/​​

【示例】

【代码】admin

import java.util.*;
// 2023-1-15

class Solution {
    public int search(int[] nums, int target) {
        Arrays.sort(nums);
        int mid = check(nums, target);
//        System.out.println(mid);
        return mid;
    }

    private int check(int[] nums, int target) {
        int start = 0;
        int end = nums.length;
        // start始终小于end
        while (start < end){
            int mid = (start + end) / 2;
            if (nums[mid] < target){
                start = mid + 1;
            }else if(nums[mid] > target){
                end = mid;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
public class Main {
    public static void main(String[] args) {
        new Solution().search(new int[]{-1,0,3,5,9,12}, 9); // 输出: 4
        new Solution().search(new int[]{-1,0,3,5,9,12}, 2); // 输出: -1
    }
}

【代码】admin

import java.util.*;
// 2023-1-15

class Solution {
    public int search(int[] nums, int target) {
        Arrays.sort(nums);
        int start = 0;
        // 这里是下标, 所以要减1
        int end = nums.length - 1;
        int mid = check(nums, target, start, end);
        System.out.println(mid);
        return mid;
    }

    private int check(int[] nums, int target, int start, int end) {
        // 如果end < start 结束
        if (end < start) return -1;
        int mid = (start + end) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] >= target){
            return check(nums, target, start, mid - 1);
        }
        if (nums[mid] < target){
            return check(nums, target, mid + 1, end);
        }
        return -1;
    }
}
public class Main {
    public static void main(String[] args) {
        new Solution().search(new int[]{-1,0,3,5,9,12}, 9); // 输出: 4
        new Solution().search(new int[]{-1,0,3,5,9,12}, 2); // 输出: -1
        new Solution().search(new int[]{-1,0,3,5,9,12}, 13); // 输出: -1
    }
}