JavafirstPosition算法

Question

int firstPosition(int x, int [] a) {

    int lower = 0;
    int upper = a.length;

    while (lower != upper) {
    int mid = (lower + upper) / 2;

    **if (x <= a[mid]) {** // the line I don't understand
    upper = mid;
    } else {
    lower = mid + 1;
    }
    return (lower);
}

如果 a = {4, 4, 5, 5, 6, 7, 8, 9, 9, 9} 对于以下 x 选择，算法将返回什么？

i) x = 3

ii) x = 4

iii) x = 5

iv) x = 9

v) x = 11

我尝试过单步执行这个程序，例如 x = 3，a.length 返回 10，因此 upper 始终等于 10。

while ( 3 ! = 0 ) { // execute line

int mid = lower + upper / 2 - which is (0 + 10)/2 = 5

if ( x <= a[mid]) // I assume that means if 3 is less than or equal to 5? 5 then replace mid with 5 and then...

lower = mid + 1 // 5+1 = 6, return 6 as lower?

Answer 1

这是一个基本的binary search算法，以迭代方式而不是递归方式实现。

您不理解的行检查是否 x (搜索值)可能位于数组的下半部分或上半部分。这是有效的，因为数组已排序。我们可以将任何已排序的数组分成两半，然后查看中间的值来确定我们要查找的值可能位于哪一半。

---

假设数组如下所示:

+---+---+---+---+---+----+
| 1 | 3 | 5 | 7 | 9 | 11 |
+---+---+---+---+---+----+
  ^                        ^
  |                        |
lower                    upper

我们正在尝试找出数字 9 是哪个槽位。由于数组已排序，我们可以立即丢弃数组的一半。

如何？

查看数组“中心”的值:它是 5 ，和9大于5 ，所以我们知道9 必须位于数组的上半部分。从算法上来说，这将是 else案例if代码中的声明。

所以我们重复相同的过程，但这次只查看数组的上半部分:

+---+---+---+---+---+----+
| 1 | 3 | 5 | 7 | 9 | 11 |
+---+---+---+---+---+----+
              ^            ^
              |            |
            lower        upper