java从一个有序数组中找出目标元素在数组中的出现的首次和最后一次位置

「爱情、让人受尽委屈。」 2023-03-13 15:29 14阅读 0赞

从一个有序数组中找出目标元素在数组中的出现的首次和最后一次位置  
要求时间复杂度O(logn)

int\[\] nums=\{1,2,3,4,5,6,7,8,8,8,8,9,10\};

这里因为是有序数组所以可以采用二分法来解决，分别找出第一次出现的位置和最后一次出现的位置  
选出中间位置开始往两边走，不断的去找与目标元素相同的数的位置，如果没有则返回-1，有则返回位置下标  
需要注意的是在找最后一次出现的时候，中间数的位置mid要+1，对应的边界也会发生相应变化，要不会越界

package com.evan.springboot.study;
    
    /**
     * @author evanYang
     * @version 1.0
     * @date 2020/5/15 下午 6:05
     */
    public class SearchDemo { 
        public static void main(String[] args) { 
            int[] nums={ 1,2,3,4,5,6,7,8,8,8,8,9,10};
            int i = searchFirst(nums, 8);
            System.out.println(i);
            int last = searchLast(nums, 8);
            System.out.println(last);
        }
    
        public static int searchFirst(int nums[],int target){ 
            int left=0;
            int right=nums.length-1;
            int mid=0;
            while (left<=right){ 
                mid=(right+left)/2;
                if(target>nums[mid]){ 
                    left=mid+1;
                }else{ 
                    right=mid;
                }
                if(right==left){ 
                    break;
                }
            }
            if (nums[left]!=target){ 
                return -1;
            }else{ 
                return left;
            }
        }
    
    
        public static int searchLast(int nums[],int target){ 
            int left=0;
            int right=nums.length-1;
            int mid=0;
            while (left<=right){ 
                mid=(right+left)/2+1;
                if(target>=nums[mid]){ 
                    left=mid;
                }else{ 
                    right=mid-1;
                }
                if(right==left){ 
                    break;
                }
            }
            if (nums[right]!=target){ 
                return -1;
            }else{ 
                return right;
            }
        }
    
    }