SimuVedaAlgorithms Lab Open in the lab

Searching / Intermediate

First and Last Position of a Value Visualizer

Run binary search twice. When you hit the target, do not stop: remember the index, then keep going left to find the first copy, or right to find the last.

Start the First and Last Position of a Value simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(log n)
Average timeO(log n)
Worst timeO(log n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Two binary searches for 8: one for the first copy, one for the last. [5, 7, 7, 8, 8, 8, 10, 12]
  2. Search for the first 8.
  3. Middle of [0..7] is index 3, value 8.
  4. Found 8 at 3. Remember it, then look further left for an earlier copy.
  5. Middle of [0..2] is index 1, value 7.
  6. 7 < 8: go right.
  7. Middle of [2..2] is index 2, value 7.
  8. 7 < 8: go right.
  9. The first 8 is at index 3.
  10. Search for the last 8.
  11. Middle of [0..7] is index 3, value 8.
  12. Found 8 at 3. Remember it, then look further right for a later copy.
  13. Middle of [4..7] is index 5, value 8.
  14. Found 8 at 5. Remember it, then look further right for a later copy.
  15. Middle of [6..7] is index 6, value 10.
  16. 10 > 8: go left.
  17. The last 8 is at index 5.
  18. Answer [3, 5]: 8 appears 3 times.

Try it with your own input →

First and last position of a value in Java, Python, C++, C and JavaScript

int[] searchRange(int[] a, int t) {
  return new int[]{ bound(a, t, true), bound(a, t, false) };
}
int bound(int[] a, int t, boolean first) {
  int lo = 0, hi = a.length - 1, ans = -1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == t) {
      ans = mid;
      if (first) hi = mid - 1; else lo = mid + 1;
    } else if (a[mid] < t) lo = mid + 1;
    else hi = mid - 1;
  }
  return ans;
}
def search_range(a, t):
    return [bound(a, t, True), bound(a, t, False)]

def bound(a, t, first):
    lo, hi, ans = 0, len(a) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == t:
            ans = mid
            if first:
                hi = mid - 1
            else:
                lo = mid + 1
        elif a[mid] < t:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans
int bound(const vector<int>& a, int t, bool first);

vector<int> searchRange(const vector<int>& a, int t) {
  return { bound(a, t, true), bound(a, t, false) };
}
int bound(const vector<int>& a, int t, bool first) {
  int lo = 0, hi = (int)a.size() - 1, ans = -1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == t) {
      ans = mid;
      if (first) hi = mid - 1; else lo = mid + 1;
    } else if (a[mid] < t) lo = mid + 1;
    else hi = mid - 1;
  }
  return ans;
}
int bound(int a[], int n, int t, int first);

void searchRange(int a[], int n, int t, int out[2]) {
  out[0] = bound(a, n, t, 1);
  out[1] = bound(a, n, t, 0);
}
int bound(int a[], int n, int t, int first) {
  int lo = 0, hi = n - 1, ans = -1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == t) {
      ans = mid;
      if (first) hi = mid - 1; else lo = mid + 1;
    } else if (a[mid] < t) lo = mid + 1;
    else hi = mid - 1;
  }
  return ans;
}
function searchRange(a, t) {
  return [bound(a, t, true), bound(a, t, false)];
}
function bound(a, t, first) {
  let lo = 0, hi = a.length - 1, ans = -1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] === t) {
      ans = mid;
      if (first) hi = mid - 1; else lo = mid + 1;
    } else if (a[mid] < t) lo = mid + 1;
    else hi = mid - 1;
  }
  return ans;
}

In an interview

LeetCode 34, Find First and Last Position of Element in Sorted Array, in O(log n).

These are lower bound and upper bound. last − first + 1 is how many times the value appears, still in O(log n).

More searching