在有序可重复数组查找

发表于 | 分类于 |
字数统计: 308 字 | 阅读时长 ≈ 1 分钟

含重复元素，求=target的最小一个

给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1

例如：[2,4,6,8,8,8,9] 求8得最小位置3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function search1(arr, target) {
  let i = 0,
    j = arr.length - 1;
  while (i <= j) {
    let mid = i + Math.floor((j - i) / 2);
    if (arr[mid] == target) {
      if (mid > 0 && arr[mid - 1] == target) {
        j = mid - 1;
      } else {
        return mid;
      }
    } else if (arr[mid] < target)
      i = mid + 1;
    else {
      j = mid - 1;
    }
  }
  return -1;
}
search1([1, 2, 3, 5, 6, 7, 7, 10], 7) // 5

含重复元素，求=target的最大一个

给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1

例如：A[2,4,6,8,8,8,9]求8得最大位置5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function search2(arr, target) {
  let i = 0,
    j = arr.length - 1;
  while (i <= j) {
    let mid = i + Math.floor((j - i) / 2);
    if (arr[mid] == target) {
      if (mid < arr.length - 1 && arr[mid + 1] == target) {
        i = mid + 1;
      } else {
        return mid;
      }
    } else if (arr[mid] < target)
      i = mid + 1;
    else {
      j = mid - 1;
    }
  }
  return -1;
}
search2([1, 2, 3, 5, 6, 7, 7, 10], 7) // 6

参考文章

二分查找问题全集OK