Learn-dsa..in 30 days!



























CC-11 : Find first and last index of number in an array.

Description:

Given a sorted input array and an element to be searched, search the index of first and last occurrence of required element in the input array using search.

Test cases and expected outputs:

Input Parameters Expected outputs
Array:
3, 22, 44, 77, 77, 77, 122, 144, 201, 		First position of 77 is 3
Last position of 77 is 5
First position of 144 is 7
Last position of 144 is 7

Pseudocode:

findFirstPos(nums[], tosearch):

Integer array named nums and integer named toSearch to be searched are received as input parameters.
Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.
Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.
Set integer variable numIdx to -1, we will use this variable to store first position of toSearch in nums.
While (firstIdx <= lastIdx) do the following steps:
Set integer variable midCount to (lastIdx-firstIdx)/2.
Set integer variable midIdx to (firstIdx+midCount)to get mid index of current partition. We will use midIdx to partition the array into 2 parts.
If (nums[midIdx]==toSearch) :
Set numIdx to midIdx; this means have found the required element.
Set lastIdx to midIdx-1.
Else if nums[midIdx] > toSearch then:
Set lastIdx=(midIdx-1) as we need to search in lower partition now.
Else:
Set firstIdx=midIdx+1, as we need to search in the higher partition now.
Return numIdx as it contains the first position of toSearch in nums.

findlastPos(nums[], tosearch):

Integer array named nums and integer named toSearch to be searched are received as input parameters.
Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.
Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.
Set integer variable numIdx to -1, we will use this variable to store first position of toSearch in nums.
While (firstIdx <= lastIdx) do the following steps:
Set integer variable midCount to (lastIdx-firstIdx)/2.
Set integer variable midIdx to (firstIdx+midCount)to get mid index of current partition. We will use midIdx to partition the array into 2 parts.
If (nums[midIdx]==toSearch) :
Set numIdx to midIdx; this means have found the required element.
Set firstIdx to midIdx-1.
Else if nums[midIdx] > toSearch then:
Set lastIdx=(midIdx-1) as we need to search in lower partition now.
Else:
Set firstIdx=midIdx+1, as we need to search in the higher partition now.
Return numIdx as it contains the first position of toSearch in nums.

Code:

public int findFirstPos(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	int numIdx=-1;
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if (nums[midIdx]==toSearch) {
			numIdx=midIdx;
			lastIdx=midIdx-1;
		} else { if (nums[midIdx]> toSearch) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return numIdx;
}

public int findLastPos(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	int numIdx=-1;
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if (nums[midIdx]==toSearch) {
			numIdx=midIdx;
			firstIdx=midIdx+1;
		} else { if (nums[midIdx]> toSearch) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return numIdx;
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us