2分搜索
21 minute read ∼ Filed in : coding1. search for range
func search(nums []int, target int) int {
left := 0
right := len(nums)-1
// must == mid, otherwise it's not log(n)
for left+1 < right{
mid := (left + right) / 2
if nums[mid] == target{
return mid
}else if nums[mid] < target {
left = mid
}else{
right = mid
}
}
if nums[left] == target{
return left
}
if nums[right] == target{
return right
}
return -1
}
2. Search Insert Position
func searchInsert(nums []int, target int) int {
left := 0
right := len(nums)-1
for left + 1< right{
mid := (left + right)/2
if nums[mid] < target{
left=mid
}else{
right=mid
}
}
if nums[left] >= target{
return left
}else if nums[right] >= target{
return right
}else{
return right+1
}
}
3. Search a 2D Matrix
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)-1
n := len(matrix[0])-1
target_row := -1
for i:=0;i<=m;i++{
if matrix[i][n] >= target{
target_row = i
break
}
}
if target_row == -1{
return false
}
// do a binary search at target row
left := 0
right := n
for left + 1 < right{
mid := (left+right)/2
if matrix[target_row][mid] == target{
return true
}else if matrix[target_row][mid] > target{
right = mid
}else{
left = mid
}
}
if matrix[target_row][left] == target || matrix[target_row][right] == target{
return true
}
return false
}
4. Find First and Last Position of Element in Sorted Array
func searchRange(nums []int, target int) []int {
l := -1
r := -1
if len(nums) == 0{
return []int{l,r}
}
// twice binary search, left bound
left := 0
right := len(nums)-1
for left + 1 < right{
mid := (left+right)/2
if nums[mid] >= target{
right = mid
}else{
left = mid
}
}
if nums[left] > target{
return []int{l,r}
}
if nums[right] < target{
return []int{l,r}
}
// use, else if else, otherwise ,l is re-writen
if nums[left] == target{
l = left
}else if nums[right] == target{
l = right
}
// twice binary search, right bound
left = 0
right = len(nums)-1
for left + 1 < right{
mid := (left+right)/2
if nums[mid] <= target{
left = mid
}else{
right = mid
}
}
if nums[left] == target{
r = left
}
if nums[right] == target{
r = right
}
return []int{l, r}
}
5. First Bad Version
func firstBadVersion(n int) int {
left := 1
right := n
// if using righ++ or left ++, it will timeout
for left + 1 < right{
mid := (left + right)/2
if isBadVersion(mid) {
right = mid
}else{
left = mid
}
}
if isBadVersion(left){
return left
}else{
return right
}
}
6. Find Minimum in Rotated Sorted Array
func findMin(nums []int) int {
left := 0
right := len(nums)-1
for left + 1 < right {
mid := (left + right)/2
if nums[mid] > nums[len(nums)-1]{
left = mid
}else if nums[mid] < nums[len(nums)-1]{
right = mid
}
}
if nums[left] < nums[right]{
return nums[left]
}else{
return nums[right]
}
}
7. Find Minimum in Rotated Sorted Array II（带重复的旋转数组，如果mid和最右值相等，绝对有一边的值全都一样）
func findMin(nums []int) int {
left := 0
right := len(nums)-1
// binary search
for left + 1 < right{
mid := (left + right)/2
if nums[mid] > nums[len(nums)-1]{
left = mid
}else if nums[mid] < nums[len(nums)-1]{
right = mid
// if equal, go through left and right
}else{
if findMinHelper(nums, mid, &left, &right){
return nums[mid]
}
}
}
if nums[left] < nums[right]{
return nums[left]
}else{
return nums[right]
}
}
// if [3 1 3 3] or [3 3 1 3]
// go through left and right, until find min value,
// if return true, means all value are the same, nums is like [ 1 1 1] etc
// if return false, still need to use binary search
func findMinHelper(nums []int, mid int, left *int, right *int) bool{
for i := mid; i < len(nums)-1; i++{
if nums[i] > nums[i+1]{
*left = mid
return false
}
}
for j := mid; j >0; j--{
if nums[j] > nums[j-1]{
*right = mid
return false
}
}
return true
}
8. Search in Rotated Sorted Array
func search(nums []int, target int) int {
left := 0
right := len(nums)-1
for left + 1 < right{
mid := (left+right)/2
if nums[mid] == target{
return mid
// if not equal, 分4段，根据mid和左右边界，来定界target的位置
}else{
if nums[len(nums)-1] < nums[mid]{
if target < nums[mid] && target >= nums[0] {
right = mid
}else{
left = mid
}
}else {
if target > nums[mid] && target <= nums[len(nums)-1]{
left = mid
} else{
right = mid
}
}
}
}
if nums[left] == target{
return left
}
if nums[right] == target{
return right
}
return -1
}
9. Search in Rotated Sorted Array II带重复的旋转数组，如果mid和最右值相等，绝对有一边的值全都一样）
func search(nums []int, target int) bool {
left := 0
right := len(nums)-1
for left + 1 < right {
mid := (left + right)/2
if nums[mid] == target{
return true
}else{
if nums[mid] > nums[len(nums)-1]{
if target < nums[mid] && target >= nums[0]{
right = mid
}else{
left = mid
}
}else if nums[mid] < nums[len(nums)-1]{
if target > nums[mid] && target <= nums[len(nums)-1]{
left = mid
}else{
right = mid
}
//如果等于，开始左右遍历
}else{
if helper(nums, &left, &right, mid){
return false
}
}
}
}
if nums[left] == target || nums[right] == target{
return true
}else{
return false
}
}
// 找到第一个不相等的
func helper(nums []int, left *int, right *int, mid int) bool{
for i:=mid; i<len(nums)-1; i++{
if nums[i] != nums[i+1]{
*left = mid
return false
}
}
for j:=mid; j>0; j--{
if nums[j] != nums[j-1]{
*right = mid
return false
}
}
return true
}
10. Find Peak Element
func findPeakElement(nums []int) int {
if len(nums) ==1{
return 0
}
left := 0
right := len(nums)-1
for left + 1 < right{
mid := (left + right)/2
// 2 分搜索，
if nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]{
return mid
}else if nums[mid] > nums[mid-1]{
left = mid
}else{
right = mid
}
}
if nums[left] > nums[right]{
return left
}else{
return right
}
}
11. Find K Closest Elements
func findClosestElements(arr []int, k int, x int) []int {
// binary search find most close value to x
left := 0
right := len(arr)-1
var pos int
for left + 1 < right{
mid := (left + right)/2
if arr[mid] == x{
pos = mid
break
}else if arr[mid] > x{
right = mid
}else{
left = mid
}
}
// two pointer, find most recent value
lp := 0
rp := 0
if pos==0{
lp = left
rp = right
}else{
lp = pos
rp = pos+1
}
var res []int
// append most recent value to res
for len(res) !=k{
res = append(res, closer(arr, &lp, &rp, x))
}
// do a sort
sort.Ints(res)
return res
}
func closer(arr []int, i *int, j *int, x int) int {
// if either i or j reach bound, only use another one
if *i < 0 && *j <= len(arr)-1{
res := arr[*j]
*j++
return res
}else if *i >= 0 && *j > len(arr)-1{
res := arr[*i]
*i--
return res
}
// if not, append the most recent value
a := arr[*i]
b := arr[*j]
if abs(a-x) < abs(b-x){
*i--
return a
}else if abs(a-x) > abs(b-x){
*j++
return b
}else{
if *i<*j{
*i--
return a
}else{
*j++
return b
}
}
}
func abs(a int)int{
if a<0{
return -a
}else{
return a
}
}
12. Closest Binary Search Tree Value
func closestValue(root *TreeNode, target float64) int {
var res int
dist := math.MaxFloat64
for root!=nil{
// check distance of each node
tmp := abs(float64(root.Val) - target)
if tmp < dist{
dist = tmp
res = root.Val
}
if target >= float64(root.Val){
root = root.Right
}else{
root = root.Left
}
}
return res
}
func abs(a float64)float64{
if a>0{return a}else{return -a}
}
13. 在大数组中查找
给一个按照升序排序的非负整数数组。这个数组很大以至于你只能通过固定的接口 ArrayReader.get(k) 来访问第k个数(或者C++里是ArrayReader->get(k))，并且你也没有办法得知这个数组有多大。
找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。
如果找不到target，返回-1。
样例 样例 1:
输入: [1, 3, 6, 9, 21, …], target = 3 输出: 1 样例 2:
输入: [1, 3, 6, 9, 21, …], target = 4 输出: -1 挑战 O(logn)的时间复杂度，n是target第一次出现的下标。
如果你访问了一个不可访问的下标（比如越界），ArrayReader 会返回2147483647。
type ArrayReader struct {}
func (this *ArrayReader) get(index int) int {return 1}
func search(reader ArrayReader, target int) int {
// You may assume all integers in the array are less than 10000
// 第一次二分搜索找边界
left := 0
right := 10000
for left+1<right{
mid := (left+right)/2
if reader.get(mid) < 2147483647{
left = mid
}else{
right=mid
}
}
if reader.get(right)<2147483647{
right = right
}else if reader.get(left)<2147483647{
right = left
}
left = 0
// 第二次二分搜索找值
for left+1<right{
mid := (left+right)/2
if reader.get(mid)>target{
right = mid
}else if reader.get(mid)<target {
left = mid
}else{
return mid
}
}
if reader.get(right)==target{
return right
}else if reader.get(left)==target{
return left
}else{
return -1
}
}
14. Pow(x, n)
func myPow(x float64, n int) float64 {
if n > 0{
return helper(x, n)
}else{
return 1/helper(x, -n)
}
}
func helper(x float64, n int)float64{
if n == 0{return 1}
y := helper(x, n/2)
if n % 2 == 0{
return y*y
}else{
return y*y*x
}
}