目录 1- 思路 2- 实现 ⭐34. 在排序数组中查找元素的第一个和最后一个位置——题解思路 3- ACM 实现
原题链接:34. 在排序数组中查找元素的第一个和最后一个位置
1- 思路
二分 - 左侧二分 + 右侧二分
右区间二分 ——> 找首次出现的位置 ——>nums[mid] >= target
左区间二分 ——> 找最后一次出现的位置 ——> **nums**[mid] <= target
2- 实现
⭐34. 在排序数组中查找元素的第一个和最后一个位置——题解思路
class Solution { public int [ ] searchRange ( int [ ] nums, int target) { int [ ] res = new int [ 2 ] ; Arrays . fill ( res, - 1 ) ; if ( nums. length == 0 || nums== null ) { return res; } int left = 0 ; int right = nums. length- 1 ; while ( left< right) { int mid = ( left+ right) / 2 ; if ( nums[ mid] >= target) { right = mid; } else { left = mid+ 1 ; } } if ( nums[ left] == target) { res[ 0 ] = left; } left = 0 ; right = nums. length- 1 ; while ( left< right) { int mid = ( left+ right+ 1 ) / 2 ; if ( nums[ mid] <= target) { left = mid; } else { right = mid- 1 ; } } if ( nums[ left] == target) { res[ 1 ] = left; } return res; }
}
3- ACM 实现
public class findFirstAndLast { public static int [ ] finFAndL ( int [ ] nums, int target) { int [ ] res = new int [ 2 ] ; Arrays . fill ( res, - 1 ) ; int left = 0 ; int right = nums. length- 1 ; while ( left< right) { int mid = ( left+ right) / 2 ; if ( nums[ mid] >= target) { right = mid; } else { left = mid+ 1 ; } } if ( res[ left] == target) { res[ 0 ] = left; } left = 0 ; right = nums. length- 1 ; while ( left< right) { int mid = ( left+ right+ 1 ) / 2 ; if ( nums[ mid] <= target) { left = mid; } else { right = mid- 1 ; } } if ( res[ left] == target) { res[ 1 ] = left; } return res; } public static void main ( String [ ] args) { Scanner sc = new Scanner ( System . in) ; String input = sc. nextLine ( ) ; input = input. substring ( 1 , input. length ( ) - 1 ) ; String [ ] parts = input. split ( "," ) ; int [ ] nums = new int [ parts. length] ; for ( int i = 0 ; i < nums. length; i++ ) { nums[ i] = Integer . parseInt ( parts[ i] ) ; } System . out. println ( "输入target" ) ; int target = sc. nextInt ( ) ; int [ ] res = finFAndL ( nums, target) ; System . out. println ( "结果是" + res[ 0 ] + " " + res[ 1 ] ) ; }
}