{"id":2414,"date":"2024-03-19T15:00:00","date_gmt":"2024-03-19T15:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2414"},"modified":"2024-03-21T08:08:30","modified_gmt":"2024-03-21T08:08:30","slug":"first-and-last-position-element-sorted-array","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/first-and-last-position-element-sorted-array\/","title":{"rendered":"How to Find First & Last Position of Element in Sorted Array?"},"content":{"rendered":"\n

Binary Search is one of the most important topics asked in interviews. It helps you to find the targeted value in O(log(n)) time complexity. The only condition is that the array should be sorted. In this article, we will learn how to find the First and Last Positions of Elements in a Sorted Array with implementation in C++, Java, and Python.<\/p>\n\n\n\n

First and Last Position Of Elements in Sorted Array<\/strong><\/h2>\n\n\n\n

In this problem, we are given a sorted array and a target element. We have to find its first and the last position in the array. It might be possible that the element is not contained in the array. In that case, you will return [-1, -1]. <\/strong><\/p>\n\n\n\n

Let\u2019s understand this with an example.<\/p>\n\n\n\n

Input:<\/strong> array = [2, 3, 4, 4, 4, 5, 6, 6], tar = 4<\/p>\n\n\n\n

Output:<\/strong> [2, 4]<\/p>\n\n\n\n

Explanation:<\/strong> We found the first 4 at index 2 and the last at index 4.<\/p>\n\n\n\n

\"first<\/figure>\n\n\n\n

Input:<\/strong> array = [2, 3, 4, 4] tar = 3<\/p>\n\n\n\n

Output:<\/strong> [1, 1]<\/p>\n\n\n\n

Explanation:<\/strong> Only one 3 is present in the whole array so the first and the last position of 3 is 1.<\/p>\n\n\n\n

The naive approach is to iterate the whole array and find the first and last position of the element. In this approach, you have to check every element present in the array which is laid to O(n) time complexity. Here’s how we will do it:<\/p>\n\n\n\n

    \n
  1. First, create two variables first and last. Initialize both with -1.<\/li>\n\n\n\n
  2. Now iterate over the array and check if the current value is the same as the target. <\/li>\n\n\n\n
  3. Update the last element with the current index.<\/li>\n\n\n\n
  4. If it is check if the value of the first variable is -1 or not. If it is updated -1 with the current index otherwise continue.<\/li>\n\n\n\n
  5. Return the first and last variable as the answer.<\/li>\n<\/ol>\n\n\n\n

    The time complexity will be O(n) where n is the size of the array. We are iterating over the array which took O(n) time complexity. The space complexity is O(1) as we are not using any extra space.<\/p>\n\n\n\n

    Optimized Binary Search Approach<\/strong><\/h2>\n\n\n\n

    In the above approach, we are using O(n) time complexity. But as we know the array is sorted so we can apply binary search on this. This will reduce our time complexity to O(log(n)). <\/p>\n\n\n\n

    We will first find the first position using binary search<\/a> and then find the last position using the same approach. Here are the steps:<\/p>\n\n\n\n

      \n
    1. First, create a function that will take an array, target, and flag. If the flag value is 0 means we are finding the first position of the target element otherwise we are finding the last position.<\/li>\n\n\n\n
    2. Now call the function for finding the first position.<\/li>\n\n\n\n
    3. Create two variables start = 0<\/strong> and end = array. size()-1<\/strong>. Now keep on iterating till the start <=end.<\/strong> <\/li>\n\n\n\n
    4. Now find the mid element by mid = (start + end)\/2. Check if the element present at the middle index is less than the target element or not.<\/li>\n\n\n\n
    5. If it is less than the target element then our target element will be present on the right side or not present at all. So we will update start = mid+1.<\/li>\n\n\n\n
    6. If it is greater than the target element then our target will be present on the left side or not present at all. So we will update end = mid-1.<\/li>\n\n\n\n
    7. If it is equal to the target then check whether we are finding the first or last position. If we are finding the first position update the end = mid-1. Otherwise update start = mid+1.<\/li>\n<\/ol>\n\n\n\n

      Let\u2019s examine the code for the above process.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Here is the C++ solution:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\n\nusing namespace std;\n\nint binary_search(vector<int>& v,int target, int p){\n\n\u00a0\u00a0\u00a0\u00a0int r=v.size();\n\n\u00a0\u00a0\u00a0\u00a0int start=0,end=r-1,ans=-1;\n\n\u00a0\u00a0\u00a0\u00a0while(start<=end){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int mid=start+((end-start)\/2);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(target > v[mid]){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0start=mid+1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else if(target < v[mid]){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0end=mid-1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans=mid;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(p)start=mid+1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else end=mid-1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0return ans;\u00a0\n\n}\n\nint main(){\n\n\u00a0\u00a0\u00a0\u00a0vector<int>arr = {2, 3, 4, 4, 4, 5, 5, 6};\n\n\u00a0\u00a0\u00a0\u00a0int target = 4;\n\n\u00a0\u00a0\u00a0\u00a0int first = binary_search(arr, target, 0);\n\n\u00a0\u00a0\u00a0\u00a0int last = binary_search(arr, target, 1);\n\n\u00a0\u00a0\u00a0\u00a0cout<<"First position of "<<target<<" is: "<<first<<endl;\n\n\u00a0\u00a0\u00a0\u00a0cout<<"Last position of "<<target<<" is: "<<last<<endl;\n\n\u00a0\u00a0\u00a0\u00a0return 0;\n\n}<\/pre><\/div>\n\n\n\n
      Java Code<\/strong><\/h3>\n\n\n\n
      Below is the Java program to find first and last position of elements in sorted array:<\/p>\n\n\n\n
      import java.util.*;\n\npublic class Main {\n\n\u00a0\u00a0\u00a0\u00a0public static int binarySearch(ArrayList<Integer> v, int target, int p) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int r = v.size();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int start = 0, end = r - 1, ans = -1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while (start <= end) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int mid = start + (end - start) \/ 2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (target > v.get(mid)) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0start = mid + 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else if (target < v.get(mid)) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0end = mid - 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans = mid;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (p == 1) start = mid + 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else end = mid - 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return ans;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(2, 3, 4, 4, 4, 5, 5, 6));\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int target = 4;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int first = binarySearch(arr, target, 0);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int last = binarySearch(arr, target, 1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0System.out.println("First position of " + target + " is: " + first);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0System.out.println("Last position of " + target + " is: " + last);\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      Here is the Python program as well:<\/p>\n\n\n\n
      def binary_search(v, target, p):\n\n\u00a0\u00a0\u00a0\u00a0r = len(v)\n\n\u00a0\u00a0\u00a0\u00a0start, end, ans = 0, r - 1, -1\n\n\u00a0\u00a0\u00a0\u00a0while start <= end:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mid = start + (end - start) \/\/ 2\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if target > v[mid]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0start = mid + 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0elif target < v[mid]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0end = mid - 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans = mid\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if p == 1:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0start = mid + 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0end = mid - 1\n\n\u00a0\u00a0\u00a0\u00a0return ans\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0arr = [2, 3, 4, 4, 4, 5, 5, 6]\n\n\u00a0\u00a0\u00a0\u00a0target = 4\n\n\u00a0\u00a0\u00a0\u00a0first = binary_search(arr, target, 0)\n\n\u00a0\u00a0\u00a0\u00a0last = binary_search(arr, target, 1)\n\n\u00a0\u00a0\u00a0\u00a0print("First position of", target, "is:", first)\n\n\u00a0\u00a0\u00a0\u00a0print("Last position of", target, "is:", last)<\/pre><\/div>\n\n\n\n
      Output: <\/strong><\/p>\n\n\n\n
      First position of 4 is: 2\nLast position of 4 is: 4<\/code><\/pre>\n\n\n\n
      The time complexity for the above code is O(log(n)). We are dividing the array into half at every step and comparing the middle value of that divided array. The space complexity is O(1) as we are not using any extra space.<\/p>\n\n\n\n
      Here is a comparison to show how the binary search approach to find in a sorted array is better:<\/p>\n\n\n\n
      Approach<\/th>Time  Complexity<\/th>Space Complexity<\/th>Description<\/th><\/tr><\/thead>
      Brute Force<\/td>O(n)<\/td>O(1)<\/td>We are iterating the whole array to find the first and the last position of the element.<\/td><\/tr>
      Binary Search <\/td>O(log(n))<\/td>O(1)<\/td>We are using binary search instead of iterating the whole array which reduces our time complexity to O(log(n)).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      In this article, we have seen various approaches for finding the first and the last positions of the element in a sorted array, which is also a leetcode problem<\/a>. We have also seen how we can reduce time complexity from O(n) to O(log(n)) with the help of binary search.<\/p>\n","protected":false},"excerpt":{"rendered":"
      We will find the first and last position of element in a sorted array using binary search, with implementation in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":2417,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2414","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2414","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2414"}],"version-history":[{"count":6,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2414\/revisions"}],"predecessor-version":[{"id":2756,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2414\/revisions\/2756"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2417"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2414"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2414"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2414"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}