package com.example.leetcode2; import java.util.*; /** * @description: 704. 二分查找 * 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 * <p> * <p> * 示例 1: * <p> * 输入: nums = [-1,0,3,5,9,12], target = 9 * 输出: 4 * 解释: 9 出现在 nums 中并且下标为 4 * 示例 2: * <p> * 输入: nums = [-1,0,3,5,9,12], target = 2 * 输出: -1 * 解释: 2 不存在 nums 中因此返回 -1 * <p> * <p> * 提示: * <p> * 你可以假设 nums 中的所有元素是不重复的。 * n 将在 [1, 10000]之间。 * nums 的每个元素都将在 [-9999, 9999]之间。 * @author: licm * @create: 2021-06-29 11:34 **/ public class Lc_704二分查找 { /** * 二分查找的注意点 * * 1.需要考虑边界,不能重复使用 ,这里使用左闭又开区间 * 2.数组要有序 * 3.如果有多个重复元素看是第一个还是最后一个,这个发生在等于目标值时的情况 * @param nums * @param target * @return */ public static int search(int[] nums, int target) { if(nums.length==0){ return -1; } int left =0; int right = nums.length-1; while (left<=right){ int mid = (left+right)/2; if(nums[mid] < target){ left = mid+1; }else if(nums[mid]>target){ right = mid-1; }else { Deque deque = new ArrayDeque(); deque.add(mid); int temp = mid-1; while(true){ if(temp<0 || nums[temp]!=target){ break; } deque.addFirst(temp); temp--; } temp = mid+1; while(true){ if(temp>nums.length-1 || nums[temp]!=target){ break; } deque.addLast(temp); temp++; } return (int)deque.getFirst(); } } return -1; } public static void main(String[] args) { int[] nums = {-1,0,3,3,3,3,5,9,12}; int target = 3; System.out.println(search(nums,target)); } }
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!