算法-二分查找#

1
// BinarySearch
2
//
3
//  @Description: 二分查找
4
//  @param nums 有序数组
5
//  @param target 目标值
6
//  @return int 目标值索引,若不存在返回-1
7
func BinarySearch(nums []int, target int) int {
8
  if len(nums) == 0 {
9
    return -1
10
  }
11
  // 初始化左右指针
12
  left := 0
13
  right := len(nums) - 1
14
  // 当右指针小于左指针时，循环结束
15
  for left <= right {
16
    // 计算中间元素的索引
17
    mid := (right-left)/2 + left
18
    if nums[mid] == target {
19
      return mid
20
    }
21
    // 当中间元素小于目标值时，移动左指针,反之移动右指针
22
    if nums[mid] < target {
23
      left = mid + 1
24
    } else {
25
      right = mid - 1
26
    }
27
  }
28
  return -1
29
}

1
// BinarySearchInsertion
2
//
3
//  @Description: 二分查找插入位置
4
//  @param nums 有序数组
5
//  @param target 目标值
6
//  @return int 插入位置下标
7
func BinarySearchInsertion(nums []int, target int) int {
8
  if len(nums) == 0 {
9
    return 0
10
  }
11
  // 初始化左右指针
12
  left := 0
13
  right := len(nums) - 1
14
  // 当右指针小于左指针时，循环结束
15
  // 此时左指针指向的元素为第一个大于目标值的元素,即插入位置
16
  for left <= right {
17
    // 计算中间元素的索引
18
    mid := (right-left)/2 + left
19
    // 当中间元素等于目标值时, 考虑到重复元素,我们规定将重复元素插入到其最左侧
20
    if nums[mid] == target {
21
      right = mid - 1
22
    } else if nums[mid] < target {
23
      left = mid + 1
24
    } else {
25
      right = mid - 1
26
    }
27
  }
28
  return left
29
}