Saturday, 5 September 2015

Finding First and Last occurrence in sorted list

Finding first and last occurrence of given number in sorted list is a very easy problem and can easily solved by leaner search with worse case Time complexity O(n) .
But We can Achieve faster search of first and last occurrence of a number by exploiting sorted feature of list.
We can  search  occurrence of any number in sorted list in O(log(n)) Time Complexity by using Binary search Algorithm.



We can Modify binary search to find first and last occurrence of number and its complexity will be O(lon(n)) .

Finding First occurrence :

  1. apply binary search to search number if found save that index as ind
  2. then search again in left sub list i.e 0 to Ind-1
  3. repeat until no occurrence of n found in left sub-list
  4. return ind 

C++ Source Code :

  1. //Find first occurence in sorted array in O(log(n))
  2. #include<iostream>
  3. #include<vector>
  4. using namespace std;
  5. int searchFirstInd(vector<int> &arr,int key,int low,int high){
  6.         //using iterative modified binary search to find fist occurrence
  7.         int mid,ind=-1;
  8.         while(low<=high){
  9.                 mid=(low+high)/2;
  10.                 if(arr[mid]==key){
  11.                         ind=mid;
  12.                         high=mid-1; //finding occurrence of first key
  13.                 }
  14.                 else if(arr[mid]<key)
  15.                         low=mid+1;
  16.                 else
  17.                         high=mid-1;
  18.         }
  19.         return ind;
  20.         //return -1 if not found
  21. }
  22. int main(){
  23.         vector<int> arr;
  24.         int n;
  25.         cout<<"Enter No of element in sorted array :";
  26.         cin>>n;
  27.         cout<<"Enter n Element: "<<endl;
  28.         int key;
  29.         for(int i=0;i<n;i++){
  30.                 cin>>key;
  31.                 arr.push_back(key);
  32.         }
  33.         cout<<"Enter key to Search its first occurrence :";
  34.         cin>>key;
  35.        
  36.         cout<<"Index of first occurrence of "<<key<<" is "<<searchFirstInd(arr,key,0,n-1);
  37. }
First Occurence

Finding Last occurrence :

  1. apply binary search to search number if found save that index as ind
  2. then search again in left sub list i.e Ind-1 to end of list
  3. repeat until no occurrence of n found in left sub-list
  4. return ind 

C++ Source Code:

  1. //Find Last occurrence in sorted array in O(log(n))
  2. #include<iostream>
  3. #include<vector>
  4. using namespace std;
  5. int searchFirstInd(vector<int> &arr,int key,int low,int high){
  6.         //using iterative modified binary search to find Last occurrence
  7.         int mid,ind=-1;
  8.         while(low<=high){
  9.                 mid=(low+high)/2;
  10.                 if(arr[mid]==key){
  11.                         ind=mid;
  12.                         low=mid+1  //finding index of last occurrence of key
  13.                 }
  14.                 else if(arr[mid]<key)
  15.                         low=mid+1;
  16.                 else
  17.                         high=mid-1;
  18.         }
  19.         return ind;
  20.         //return -1 if not found
  21. }
  22. int main(){
  23.         vector<int> arr;
  24.         int n;
  25.         cout<<"Enter No of element in sorted array :";
  26.         cin>>n;
  27.         cout<<"Enter n Element: "<<endl;
  28.         int key;
  29.         for(int i=0;i<n;i++){
  30.                 cin>>key;
  31.                 arr.push_back(key);
  32.         }
  33.         cout<<"Enter key to Search its Last occurrence :";
  34.         cin>>key;
  35.        
  36.         cout<<"Index of Last occurrence of "<<key<<" is "<<searchFirstInd(arr,key,0,n-1);
  37. }

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets