Lexi's Leetcode solutions

[phone] 一个排好序的数组,找x应该在的index

Posted on: September 3, 2013

比如{1, 2, 4, 5},3的supposed index就应该是2(把4的位置顶替了)。

facts:

  • because in the end, when p’s next is q, the mid will == p, and new left section will be [q, p](q is mid – 1 and p stays); new right section will be [q, p] (p is mid + 1 and q stays), which ever, we want to return the p because we didn’t find x!
  •  is there a possibility where in the end p’s next is not q? like p q somehow points to the same element, then it’s the same, we want to return p.
  • that’s all the possible combinations. There’s no way [p, somethinglese, q] in the end, that will always transform to scenario 1 or scenario 2.
int findSupposedIndex(int[] arr, int x, int p, int q) {
  if (p > q)
    return p;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
      return mid;
  else if (arr[mid] > x)
      return findSupposedIndex(arr, x, p, mid - 1);
  else
      return findSupposedIndex(arr, x, mid + 1, q);

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: