# 34. Find First and Last Position of Element in Sorted Array

![](/files/-MfuXoze5e25sELsy7xT)

time: O(logn)

space: O(1)

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[]{-1, -1};
        if (nums == null || nums.length == 0) return res;
        
        int first = findFirst(nums, target);
        
        if (first == -1) return res;
        
        res[0] = first;
        res[1] = findLast(nums, target);
        return res;
    }
    private int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1; // or left + (right - left)/2
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] != target ? -1 : left;
    }
    private int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1)/2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}
```

## Latest version

time: O(logn)

space: O(1)

````java
```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[] {findFirst(nums, target), findLast(nums, target)};
    }
    public int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                right = mid - 1; // when find, keep to find left
            }
        }
        if (left == nums.length) {
            return -1;
        }
        return nums[left] == target ? left : -1;
    }
    public int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                left = mid + 1; // when find, keep to find right
            }
        }
        if (left - 1 < 0) {
            return -1;
        }
        return nums[left - 1] == target ? left - 1 : -1;
    }
}
```
````

### best solution!!

````java
```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeftBound(nums, target), findRightBound(nums, target)};
    }
    public int findLeftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        int leftBound = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                leftBound = Math.min(leftBound, mid);
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return leftBound == Integer.MAX_VALUE ? -1 : leftBound;
    }
    public int findRightBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        int rightBound = Integer.MIN_VALUE;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                rightBound = Math.max(rightBound, mid);
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return rightBound == Integer.MIN_VALUE ? -1 : rightBound;
    }
}
```
````

## Best and make sense Solution

````java
```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeftMost(nums, target), findRightMost(nums, target)};
        
    }
    //[5,7,7x,8,8x,10]
    private int findLeftMost(int[] nums, int target) {
        int left = 0; //3
        int right = nums.length-1; //5
        
        while (left <= right) {
            int mid = left + (right - left)/2; // 3 + (5-3)/2 = 4
            if (nums[mid] == target) {
                if (mid-1 >= 0 && nums[mid-1] == target) {
                    right = mid - 1; // 左邊還有一樣的, 往左找
                } else {
                    return mid;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    private int findRightMost(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        
        while (left <= right) {
            int mid = left + (right - left)/2; // 1
            if (nums[mid] == target) {
                if (mid+1 < nums.length && nums[mid+1] == target) {
                    left = mid + 1; // 右邊還有一樣的, 往右找
                } else {
                    return mid;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/binary-search/34.-find-first-and-last-position-of-element-in-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.