Linkedin Interview Question Software Engineer in Tests
Country: United States
Interview Type: Phone Interview
There is a lot of redundancy in the code, you can combine the logic and use it in one method.
class BinarySearch{
public static void main (String []args){
int []a = {0,0,2,3,3,3,3,4,7,7,9};
int result[] = binarySearchModified(a,3);
System.out.println("{" + result[0] +"," + result[1] +"}");
result = binarySearchModified(a,5);
System.out.println("{" + result[0] +"," + result[1] +"}");
}
// The idea is to return an array containing two elements with lowerIndex and higherIndex
public static int[] binarySearchModified(int []input, int target){
int low =0, high=input.length-1,mid, highIndex;
int result[] ={-1,-1};
while(low<=high){
mid = low + (high-low)/2;
if(target == input[mid]){ // Once the target is reached, just check for the range
highIndex = mid;
while( mid!=0 && target == input[mid-1]) //loop over until target repeats, thereby finding higher index
mid--;
result[0] = mid;
while( highIndex != input.length-1 && target == input[highIndex+1] )
highIndex++;
result[1] = highIndex;
return result; //Return the result
}
if(target > input[mid])
low = mid+1;
else if(target < input[mid])
high = mid-1;
}
return result; // Target is not found.
}
}
public static int[] findBinarySearch(int[] input, int target){
int start = -1;
int end = -1;
int[] result = {start, end};
int low = 0;
int high = input.length -1;
while(low <= high){
int mid = (low + high)/2;
if(input[mid] == target){
while(input[mid] == target ){
mid --;
}
start = mid + 1;
mid++;
while(input[mid] == target){
mid ++;
}
end = mid - 1;
result[0] = start;
result[1] = end;
return result;
}
if(target > input[mid]){
low = mid + 1;
}else{
high = mid -1;
}
}
return result;
}
I'm new to this community. I see the answers were down voted but couldnt get the reason. When down voting, wouldn't they describe why it was down voted?
//If the element is not present in the array I printed that array is not present rather printing -1 -1 , it's an easy thing to change
/*Given a sorted integer array and a number, find the start and end indexes of the number in the array.
Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}
Complexity should be less than O(n)
Developed by : Suman Roy
Email: email.suman.roy@gmail.com
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
int MAX,MIN;
bool flag1=false;
bool flag2=false;
void Search(int *array , int i_start , int i_end , int i_search){
if ( flag1 & flag2 )
exit( EXIT_SUCCESS);
// std::cout<<"start ="<<i_start<<"end ="<<i_end<<std::endl;
int i_mid= ( i_start+i_end ) /2;
// std::cout<<"Mid= "<<i_mid<<":"<<array[i_mid]<<std::endl;
if ( array[i_mid ] == i_search) {
if ( ( array [ i_mid - 1 ] !=i_search || i_mid==0 ) & !flag1 ){
std::cout<<"left_index= "<< i_mid<<std::endl;
flag1=true;
Search( array , i_mid + 1 , MAX , i_search );
std::cout<<"Rightindex = "<<i_mid<<std::endl;
flag2=true;
exit(EXIT_SUCCESS);
return ;
} if( !flag1 ){ Search ( array , MIN ,i_mid -1 , i_search ); }
if ( (array [ i_mid +1 ] !=i_search || i_mid == MAX ) & !flag2){
std::cout<<"right_index= "<<i_mid<<std::endl;
flag2=true;
Search ( array , MIN , i_mid-1 , i_search ) ;
std::cout<<"Left index="<<i_mid<<std::endl;
flag1=true;
exit(EXIT_SUCCESS);
return ;
}
if( !flag2 ){ Search ( array , i_mid + 1 , MAX , i_search );}
}
if( ( * ( array + i_mid ) >i_search )){
if( i_mid-1 >= i_start ){
MAX=i_mid-1;
Search ( array , i_start , i_mid-1 , i_search ) ;
}
}
else{
if( * ( array + i_mid ) < i_search ){
if( i_mid + 1 <=i_end ){
MIN=i_mid+1;
Search( array , i_mid + 1 ,i_end , i_search );
}
}
}
}
int main(){
int i_search;
MIN=0;
MAX=11;//no of elements in array
int array[]={0,0,2,3,3,3,3,3,4,7,7,9};
std::cout<<"enter the element\n";
std::cin>>i_search;
Search ( array , MIN ,MAX , i_search );
std::cout<<"Element not present\n";
}
Out Put:
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
1
Element not present
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
0
left_index= 0
right_index= 1
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
2
left_index= 2
Rightindex = 2
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
3
left_index= 3
right_index= 7
suman@suman-laptop:/media/D/coding/algo/search$
public static void FindIndex(int[] arr, int findNumber)
{
int count = 0;
foreach (int i in arr)
{
if (i == findNumber)
{ count++; }
}
if (count == 0)
{
Console.WriteLine("Output = {-1,-1}");
Console.ReadKey();
}
else
{
for (int i = 0; i < arr.Length; i++)
{
while (findNumber == arr[i])
{
Console.WriteLine("Output = {"+i+","+(i+count-1)+"}");
Console.ReadKey();
return;
}
}
}
}
I see very big length of codes here... I always try to simplify the procedure as much as possible. This codes seems to be working fine.
#include <iostream>
using namespace std;
#define MAX 5
int index[2], i;
void functionIndexFind(int arr[MAX], int num) {
bool chk = false;
for (i=0; i<MAX; i++)
{
if((arr[i]==num) && (chk==false)) {
index[0] = i+1;
chk = true;
}
if((arr[i]==num) && (chk==true)) {
index[1] = i+1;
}
else
continue;
}
}
int main(){
int array[MAX] = {2,3,4,8,2};
functionIndexFind(array, 2);
cout << index[0] << index[1];
return 0;
}
Algorithm:
1) Find occurrence of the key using binary search
2) As soon as you find this occurrence, mark the last array (indices) where you found this first occurrence > Let us call this a subarray. To make it clear, subarray is the array that we found the key, that means subarray[mid] = key.
3) No do again a binary search in the first half of this array to find the first occurrence of the key.
4) Do a binary search, similar to #3 to find the last index.
Here is the code in java:
public class FirstAndLastIndex {
private static int intr_f_index,intr_l_index,key;
public static void main(String args[]){
int[] inparray = {1,2,4,6,6,6,6,6,6,7,12,14,14,14,14,14,14,14,14,14,14,14,14,300};
int index,firstindex,lastindex,arrfindex,arrlindex,n;
key = 14;
n = inparray.length;
arrfindex = 0;
arrlindex = n-1;
index = binarySearchIndex(inparray,arrfindex,arrlindex);
if(index == -1){
firstindex =-1;
lastindex =-1;
System.out.println("{"+firstindex+","+lastindex+"}");
}
else{
firstindex = binarySearchFirstIndex(inparray,intr_f_index,index);
lastindex = binarySearchLastIndex(inparray,index,intr_l_index);
System.out.println("{"+firstindex+","+lastindex+"}");
}
}
private static int binarySearchIndex(int[] inparr, int findex, int lindex){
int mid = findex+(lindex-findex)/2;
if(findex == lindex && inparr[findex]!=key)
return -1;
if(inparr[mid] == key){
intr_f_index=findex;
intr_l_index=lindex;
return mid;
}
else if(inparr[mid] > key){
return binarySearchIndex(inparr,findex,mid-1);
}
else{
return binarySearchIndex(inparr,mid+1,lindex);
}
//return -1;
}
private static int binarySearchFirstIndex(int[] inparr,int findex,int lindex){
if(findex == lindex)
return findex;
int mid = findex+(lindex-findex)/2;
if(inparr[mid] == key){
return binarySearchFirstIndex(inparr,findex,mid);
}
else{
return binarySearchFirstIndex(inparr,mid+1,lindex);
}
}
private static int binarySearchLastIndex(int[] inparr, int findex, int lindex){
int mid;
if(findex == lindex)
return findex;
mid = findex+(lindex-findex)/2+1;
if(inparr[mid] == key){
return binarySearchLastIndex(inparr,mid,lindex);
}
else{
return binarySearchLastIndex(inparr,findex,mid-1);
}
}
}
1) First find the index of the element by using binarySearch
2) If index find by binary Search is not equal to -1 i.e. element is found then
a) Recursively find the first occurrence of element in array[start, binarySearchIndex]
b) Recursively find the last occurrence of element in array[binarySearchIndex, end]
public static int firstOccurance(int[] a, int start, int end, int key)
{
if (start > end)
{
return -1;
}
if (start == end & key == a[start])
{
return start;
}
int middle = (start + end) / 2;
if (key == a[middle])
{
return firstOccurance(a, start, middle, key);
}
else
{
return firstOccurance(a, middle + 1, end, key);
}
}
public static int lastOccurance(int[] a, int start, int end, int key)
{
if (start > end)
{
return -1;
}
if (start == end & key == a[start])
{
return start;
}
int middle = (start + end) / 2 + 1;
if (key == a[middle])
{
return lastOccurance(a, middle, end, key);
}
else
{
return lastOccurance(a, start, middle - 1, key);
}
}
public static int binarySearch(int[] a, int start, int end, int key)
{
if (end < start)
{
return -1;
}
int middle = (start + end) / 2;
if (key == a[middle])
{
return middle;
}
else if (key > a[middle])
{
return binarySearch(a, middle + 1, end, key);
}
else
{
return binarySearch(a, start, middle - 1, key);
}
}
public static int[] findRangeBinarySearch(int[] a, int key)
{
int[] result = { -1, -1 };
int binIndex = binarySearch(a, 0, a.length, key);
if (binIndex != -1)
{
result[0] = firstOccurance(a, 0, binIndex, key);
result[1] = lastOccurance(a, binIndex, a.length - 1, key);
}
return result;
}
private static void findFistAndLastIndex(int[] array, int key) {
int low = 0;
int high = array.length - 1;
int firstIndex = -1;
int lastIndex = -1;
while (low < high ) {
int mid = low + (high - low)/ 2;
if (array[mid] < key) {
low = mid + 1;
} else if (array[mid] > key) {
high = mid - 1;
} else {
firstIndex = findFirstIndex(array, low, mid);
lastIndex = findLastIndex(array, mid, high);
break;
}
}
System.out.println(firstIndex);
System.out.println(lastIndex);
}
private static int findFirstIndex(int[] array, int low, int high) {
int index = high;
int key = array[high];
while (low < high) {
int mid = low + (high - low )/2;
if (array[mid] == key) {
index = mid;
high = mid - 1;
} else if (array[mid] < key) {
low = mid + 1;
}
if (array[low] == key) {
index = low;
break;
}
}
return index;
}
private static int findLastIndex(int[] array, int low, int high) {
int index = low;
int key = array[low];
while (low < high) {
int mid = low + (high - low )/2;
if (array[mid] == key) {
index = mid;
low = mid + 1;
} else if (array[mid] > key) {
high = mid -1;
}
if (array[high] == key) {
index = high;
break;
}
}
return index;
}
two binary search
1) left edge : array[pos] == target && array[pos -1] < target
2) right edge:array[pos] == target && array[pos -1] > target
static void Main(string[] args)
{
int[] array = { 1, 2, 3, 3, 3, 3, 3, 4, 5, 6 };
int target = 3;
Console.WriteLine(FindEdge(array, 0, array.Length - 1, target, true));
Console.WriteLine(FindEdge(array, 0, array.Length - 1, target, false));
}
static int FindEdge(int[] array, int from, int to, int target, bool isLowerEdge)
{
int pos = from + (to - from) / 2;
if (pos == from && array[pos] >= target)
{
return -1;
}
if (pos == to - 1 && array[to] <= target)
{
return -1;
}
if (array[pos] == target && ((isLowerEdge && array[pos - 1] < target) || (!isLowerEdge && array[pos + 1] > target)))
{
return isLowerEdge ? pos - 1 : pos + 1;
}
else
{
if (array[pos] < target)
{
return FindEdge(array, pos + 1, to, target, isLowerEdge);
}
else if (array[pos] == target)
{
return Math.Max(FindEdge(array, from, pos, target, isLowerEdge), FindEdge(array, pos + 1, to, target, isLowerEdge));
}
else
{
return FindEdge(array, from, pos, target, isLowerEdge);
}
}
}
<?php
function fbinarysearch($inparray,$target,$start,$end,$ctr) {
echo "F COUNT:".$ctr." START:".$start." END:".$end;
if($end>=$start) {
$mid = floor(($start+$end)/2);
echo " MID:".$mid."\n";
$ctr++;
if($inparray[$mid] == $target){
$midprobe = fbinarysearch($inparray,$target,$start,$mid-1,$ctr);
if($midprobe == -1)
return $mid;
else
return $midprobe;
}
else if($inparray[$mid] > $target)
return fbinarysearch($inparray,$target,$start,$mid-1,$ctr);
else if($inparray[$mid] < $target)
return fbinarysearch($inparray,$target,$mid+1,$end,$ctr);
} else {
return -1;
}
}
function lbinarysearch($inparray,$target,$start,$end,$ctr) {
echo "L COUNT:".$ctr." START:".$start." END:".$end;
if($end>=$start) {
$mid = ceil(($start+$end)/2);
echo " MID:".$mid."\n";
$ctr++;
if($inparray[$mid] == $target){
$midprobe = lbinarysearch($inparray,$target,$mid+1,$end,$ctr);
if($midprobe == -1)
return $mid;
else
return $midprobe;
}
else if($inparray[$mid] > $target)
return lbinarysearch($inparray,$target,$start,$mid-1,$ctr);
else if($inparray[$mid] < $target)
return lbinarysearch($inparray,$target,$mid+1,$end,$ctr);
} else {
return -1;
}
}
$inparray = array(1,2,3,4,4,4,4,4,4,4,4,5,6,7);
$target = 4;
//TEST CASES
//$target = 1;
//$target = 7;
//$target = 0;
//$target = 10;
//$inparray = array(1,2,3,3,4,4,4,4,4,4,4,5,6,7);
//$target = 4;
//$inparray = array(1,2,3,4,4,4,4,4,4,4,5,5,6,7);
//$target = 4;
//$inparray = array(4,4,4,4,4,4,4,4,4,4,4,4,4,4);
//$target = 4;
$len = sizeof($inparray);
echo "BINARY SEARCH POSITION: ".binarysearch($inparray,$target,0,$len-1,0)."\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
$first = fbinarysearch($inparray,$target,0,$len-1,0);
echo "\n\nFIRST BINARY SEARCH POSITION: ".$first."\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
if($first != -1) {
$last = lbinarysearch($inparray,$target,$first,$len-1,0);
echo "\n\nLAST BINARY SEARCH POSITION: ".$last."\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
} else {
echo "\n\nLAST BINARY SEARCH POSITION: -1\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
}
print_r($inparray);
?>
void calc_range(int *sorted_array, int start, int end, int x, int *range_start, int *range_end)
{
int start_1;
int end_1;
int start_2;
int end_2;
int mid;
start_1 = end_1 = start_2 = end_2 = -1;
mid = 0;
if(start <= end)
{
mid = (start+end)/2;
if(sorted_array[mid] == x)
{
*range_start = *range_end = mid;
if(start <= mid-1)
calc_range(sorted_array, start, mid-1, x, &start_1, &end_1);
if(mid+1 <= end)
calc_range(sorted_array, mid+1, end, x, &start_2, &end_2);
if(start_1 != -1)
*range_start = start_1;
if(end_2 != -1)
*range_end = end_2;
}
else if(x < sorted_array[mid])
{
if(start <= mid-1)
calc_range(sorted_array, start, mid-1, x, &start_1, &end_1);
*range_start = start_1;
*range_end = end_1;
}
else
{
if(mid+1 <= end)
calc_range(sorted_array, mid+1, end, x, &start_2, &end_2);
*range_start = start_2;
*range_end = end_2;
}
}
}
How abut this in Java as it should be O(n) complexity.
public class FindStartEndNumberIndex {
public static void main(String[] args) {
int[] Array = { 0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9 };
findIndex(Array, 3);
findIndex(Array, 5);
}
static void findIndex(int[] array, int number) {
int startIndex = -1, endIndex = -1;
for(int i = 0; i < array.length; i++) {
if(array[i] == number) {
if(startIndex < 0) {
startIndex = i;
}
endIndex = i;
}
}
System.out.printf("{%d,%d}\n", startIndex, endIndex);
}
}
Output:
{3,6}
{-1,-1}
{{
#include <stdio.h>
#include <string.h>
/*
Given a sorted integer array and a number, find the start and end indexes of the number in the array.
Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}
Complexity should be less than O(n)
*/
int binarySearchFirst(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] < key ) {
l = m + 1;
} else {
r = m - 1;
}
}
if( arr[l] == key )
return l;
else
return -1; // Not in array
}
int binarySearchLast(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] <= key ) {
l = m + 1;
} else {
r = m - 1;
}
}
if( arr[r] == key )
return r;
else
return -1; // Not in array
}
void findIndicies(int *arr, int size, int num, int *start, int *end) {
*start = binarySearchFirst(arr, size, num);
*end = binarySearchLast(arr, size, num);
}
main()
{
int start = -1, end = -1;
int arr[] = {0,0,2,3,3,3,3,4,7,7,9};
findIndicies(arr, sizeof(arr)/sizeof(arr[0]), 9, &start, &end);
printf("start: %d end: %d", start, end);
}
}}
This program is simple and efficient. It does not handle boundary case when the key is not in the array. l/r in binarySearchFirst()/binarySearchLast() respectively could be out of bound (for example arr = {1, 1, 1}). Here is a corrected program (also taking care of indentation for clarity):
The (minor) correction is commented out. The test program illustrates the problem by printing l/r before the final compare with key.
#include <stdio.h>
#include <string.h>
/*
Given a sorted integer array and a number, find the start and end indexes of the number in the array.
Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}
Complexity should be less than O(n)
*/
int binarySearchFirst(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] < key ) {
l = m + 1;
} else {
r = m - 1;
}
}
printf("l = %d\n", l);
if( /*l < size &&*/ arr[l] == key )
return l;
else
return -1; // Not in array
}
int binarySearchLast(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] <= key ) {
l = m + 1;
} else {
r = m - 1;
}
}
printf("r = %d\n", r);
if( /*r >= 0 &&*/ arr[r] == key )
return r;
else
return -1; // Not in array
}
void findIndicies(int *arr, int size, int num, int *start, int *end) {
*start = binarySearchFirst(arr, size, num);
*end = binarySearchLast(arr, size, num);
}
main()
{
int start = -1, end = -1;
int arr[] = {1, 1, 1};
findIndicies(arr, sizeof(arr)/sizeof(arr[0]), 3, &start, &end);
printf("start: %d end: %d\n", start, end);
int arr1[] = {4, 4, 4};
findIndicies(arr1, sizeof(arr1)/sizeof(arr1[0]), 3, &start, &end);
printf("start: %d end: %d\n", start, end);
}
public static int StartIndex(int[] arr, int target){
return StartIndex(arr,target, 0, arr.length-1);
}
public static int StartIndex(int[] arr, int target, int start, int end){
if (start>end) return -1;
if (start==end){
if (arr[start]==target) return start;
else return -1;
}
if (end==start+1){
if (arr[end]==target && arr[start]!=target) return end;
else return -1;
}
int mid = (start+end)/2;
if (arr[mid]<target){
return StartIndex(arr,target,mid,end);
}
else{ //>=
return StartIndex(arr,target,start,mid);
}
}
public static int EndIndex(int[] arr, int target){
return EndIndex(arr,target, 0, arr.length-1);
}
public static int EndIndex(int[] arr, int target, int start, int end){
if (start>end) return -1;
if (start==end){
if (arr[start]==target) return start;
else return -1;
}
if (end==start+1){
if (arr[end]!=target && arr[start]==target) return start;
else if (arr[end]==target && end==arr.length-1) return end;
else return -1;
}
int mid = (start+end)/2;
if (target>=arr[mid]){
return EndIndex(arr,target,mid,end);
}
else{ //>=
return EndIndex(arr,target,start,mid);
}
}
public class Solution {
public static int[] searchRange(int[] A, int target) {
int[] ret = {Integer.MAX_VALUE, Integer.MIN_VALUE};
rec(A, target, ret, 0, A.length-1);
if(ret[0] == Integer.MAX_VALUE){
ret[0] = -1;
}
if(ret[1] == Integer.MIN_VALUE){
ret[1] = -1;
}
return ret;
}
public static void rec(int[] A, int target, int[] ret, int low, int high){
if(low > high){
return;
}
int mid = low + (high-low)/2;
if(target == A[mid]){
ret[0] = Math.min(ret[0], mid);
ret[1] = Math.max(ret[1], mid);
rec(A, target, ret, low, mid-1);
rec(A, target, ret, mid+1, high);
}else if(target < A[mid]){
rec(A, target, ret, low, mid-1);
}else{
rec(A, target, ret, mid+1, high);
}
}
}
//Time Complexity: O(n)
ArrayList<Integer> findStartEnd(ArrayList<Integer> a, k){
ArrayList<Integer> ret = new ArrayList<~>();
if(a.size() < 0) return ret;
if(a.size() == 1){
if(a[a.size()] == k){
ret.add(a.size()); ret.add(a.size());
return ret;
}
return ret;
}
boolean stop = false;
int itr = 0;
while(itr < a.size()){//check entire len
if(a[itr] == k){ //element found
if(!stop){//hitting first index
ret.add(a[itr]);
stop = true;
}
}
else {
if(stop){
ret.add(a[itr-1]);
stop = false;
}
}
itr++;
}
return ret;
}
public class BinarySearch
{
public static final int NOT_FOUND = -1;
public static int findex;
public static int lindex;
public static int fbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;
if (low<=high)
{
mid = low+(high-low) /2;
if ((a[mid]==key))
{
System.out.println(mid);
int r=1;
findex=mid;
while(low<(mid-r))
{
int z = fbinarySearch(a, key,low,mid-r);
if (z== -1) {return findex ; }
else {r++;
}
}
}
else if (a[mid] < key)
return fbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return fbinarySearch(a, key,low,mid-1);
}
return NOT_FOUND;
}
public static int lbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;
if (low<=high)
{
mid = low+(high-low) /2;
if ((a[mid]==key))
{
System.out.println(mid);
int r=1;
lindex=mid;
while(high>(mid+r))
{
int z = lbinarySearch(a, key,mid+r,high);
if (z== -1) {return lindex ; }
else {r++;
}
}
}
else if (a[mid] < key)
return lbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return lbinarySearch(a, key,low,mid-1);
}
return NOT_FOUND;
}
public static void main(String[] args)
{
double key = 10.5, index;
double a[] ={2,3,10.5,10.5,10.5,10.5,10.5,10.5, 30.5};
int i;
int l = a.length;
int j;
int low=0;
int high = a.length-1;
for (i=0;i < l;i++)
{
System.out.println(a[i]);
}
int fi=0,fl=0;
fi =fbinarySearch(a, key,low, high) ;
fl =lbinarySearch(a, key,low, high) ;
System.out.println("Found " + key + " at " + fi + " to " + fl );
}
}
this is a simple an easy to find solution :
2 different calls of binary search fr each index :
on locating key , check its left subarray for key again recursively to get findex
check right subarray for key recursively to get last index
public class BinarySearch
{
public static final int NOT_FOUND = -1;
public static int findex;
public static int lindex;
public static int fbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;
if (low<=high)
{
mid = low+(high-low) /2;
if ((a[mid]==key))
{
int r=1;
findex=mid;
while(low<(mid-r))
{
int z = fbinarySearch(a, key,low,mid-r);
if (z== -1) {return findex ; }
else {r++;
}
}
}
else if (a[mid] < key)
return fbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return fbinarySearch(a, key,low,mid-1);
}
return NOT_FOUND;
}
public static int lbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;
if (low<=high)
{
mid = low+(high-low) /2;
if ((a[mid]==key))
{
int r=1;
lindex=mid;
while(high>(mid+r))
{
int z = lbinarySearch(a, key,mid+r,high);
if (z== -1) {return lindex ; }
else {r++;
}
}
}
else if (a[mid] < key)
return lbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return lbinarySearch(a, key,low,mid-1);
}
return NOT_FOUND;
}
public static void main(String[] args)
{
double key = 10.5, index;
double a[] ={2,3,10.5,10.5,10.5,10.5,10.5,10.5, 30.5};
int i;
int l = a.length;
int j;
int low=0;
int high = a.length-1;
for (i=0;i < l;i++)
{
System.out.println(a[i]);
}
int fi=0,fl=0;
fi =fbinarySearch(a, key,low, high) ;
fl =lbinarySearch(a, key,low, high) ;
System.out.println("Found " + key + " at " + fi + " to " + fl );
}
}
better solution :
find mid of key
check left subarray for occurences of key , if present , repeat till not present :mid of the prev iteration (2nd last ) is startindex
same for righ subarray and lastindex
public class BinarySearch
{
public static final int NOT_FOUND = -1;
public static int findex;
public static int lindex;
public static int fbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;
if (low<=high)
{
mid = low+(high-low) /2;
if ((a[mid]==key))
{
findex=mid;
while(low<(mid-1))
{
int z = fbinarySearch(a, key,low,mid-1);
if (z== -1) {return findex ; }
else {
mid=z;
}
}
}
else if (a[mid] < key)
return fbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return fbinarySearch(a, key,low,mid-1);
}
return NOT_FOUND;
}
public static int lbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;
if (low<=high)
{
mid = low+(high-low) /2;
if ((a[mid]==key))
{
lindex=mid;
while(high>(mid+1))
{
int z = lbinarySearch(a, key,mid+1,high);
if (z== -1) {return lindex ; }
else {
mid=z;
}
}
}
else if (a[mid] < key)
return lbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return lbinarySearch(a, key,low,mid-1);
}
return NOT_FOUND;
}
public static void main(String[] args)
{
double key = 10.5, index;
double a[] ={2,3,10.5,10.5,10.5,10.5,10.5,10.5, 30.5};
int i;
int l = a.length;
int j;
int low=0;
int high = a.length-1;
for (i=0;i < l;i++)
{
System.out.println(a[i]);
}
int fi=0,fl=0;
fi =fbinarySearch(a, key,low, high) ;
fl =lbinarySearch(a, key,low, high) ;
System.out.println("Found " + key + " at " + fi + " to " + fl );
}
}
import java.util.Scanner;
public class StartAndEndIndexOfNumberInArray
{
public static void main(String args[])
{
int[] a = {0,0,2,3,3,3,3,4,7,7,9};
Scanner in = new Scanner(System.in);
System.out.println("Enter the number to be found: ");
int num = in.nextInt();
int low =0, high=0;
for(int i=0;i<a.length;i++)
{
if(a[i] == num)
{
low = i;
break;
}
else
low = -1;
}
for(int i=a.length - 1;i>=0;i--)
{
if(a[i] == num)
{
high = i;
break;
}
else
high = -1;
}
System.out.println("Low and High position of the number "+num+" is "+low+","+high);
}
}
public class StartAndEndIndexOfNumberInArray
{
public static void main(String args[])
{
int[] a = {0,0,2,3,3,3,3,4,7,7,9};
Scanner in = new Scanner(System.in);
System.out.println("Enter the number to be found: ");
int num = in.nextInt();
int low =0, high=0;
for(int i=0;i<a.length;i++)
{
if(a[i] == num)
{
low = i;
break;
}
else
low = -1;
}
for(int i=a.length - 1;i>=0;i--)
{
if(a[i] == num)
{
high = i;
break;
}
else
high = -1;
}
System.out.println("Low and High position of the number "+num+" is "+low+","+high);
}
}
Here is my Ruby solution:
#!/usr/bin/env ruby
class Array
def find_range_of_int(v)
i1 = self.find_index(v) || -1
i2 = i1 < 0 ? -1 : self.length - 1 - self.reverse.find_index(v)
[i1,i2]
end
end
a =
{
3 => [0,0,2,3,3,3,3,4,7,7,9],
5 => [0,0,2,3,3,3,3,4,7,7,9]
}
a.each_pair do |v,a|
i1,i2 = a.find_range_of_int(v)
puts "{#{i1},#{i2}}"
end
Here is my modified Ruby solution which executes with complexity less than O(n), in contrast to my previous posting:
#!/usr/bin/env ruby
class Array
def find_first(v,depth = 0,sign = 1)
n = self.length
p = (n/2.0).ceil - 1
return -1 if depth > 8
return p if self[p] == v && (n == 1 || self[p-1] != v)
return -1 if n == 1
i = self[0..p].find_first(v,depth + 1,sign)
return i if i >= 0
i = self[p+1..-1].find_first(v,depth + 1,sign)
return -1 if i < 0
r = p + 1 + i
return r
end
def find_last(v,depth = 0)
p = self.reverse.find_first(v,depth,sign = -1)
p = p < 0 ? p : self.length - 1 - p
return p
end
def find_range_of_int(v)
i1 = self.find_first(v)
i2 = self[i1+1..-1].find_last(v)
i2 = i2 < 0 ? i2 : i2 + i1 + 1
[i1,i2]
end
end
a =
{
3 => [0,0,2,3,3,3,3,4,7,7,9],
5 => [0,0,2,3,3,3,3,4,7,7,9]
}
a.each_pair do |v,a|
i1,i2 = a.find_range_of_int(v)
puts "a: #{a}, v: #{v} --> {#{i1},#{i2}}"
end
The output is as follows:
a: [0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9], v: 3 --> {3,6}
a: [0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9], v: 5 --> {-1,-1}
Python 3:
def find_range(a, b):
counter = [i for i in range(len(a)) if a[i] == b]
start_index = counter[0]
end_index = counter[-1]
total = len(counter)
print("start index of " + str(b) + " --> " + str(start_index) + "; end index --> " + str(end_index) + ".")
return "start index of " + str(b) + " is " + str(start_index) + " and appears " + str(total) + " times."
result = find_range([1, 2, 2, 1, 1, 1, 4], 1)
print(result)
------------------------------
Result: start index of 1 --> 0; end index --> 5.
start index of 1 is 0 and appears 4 times.
public static void main(String[] args) {
int[] numbers = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,2};
System.out.println(findLeftOccurance(numbers, 0, numbers.length-1, 1, -1, -1, -1));
}
public static int findLeftOccurance(int[] numbers, int i, int j, int number, int index, int indexLeft, int indexRight) {
int mid = i + (j - i) / 2;
if(i>j) {
return index;
}
if(numbers[mid] == number) {
index = mid;
}
if(number <= numbers[mid]) {
indexLeft = findLeftOccurance(numbers, i, mid - 1, number, index, indexLeft, indexRight);
}
if(number > numbers[mid]) {
indexRight = findLeftOccurance(numbers, mid + 1, j, number, index, indexLeft, indexRight);
}
return (indexLeft != -1 && indexRight != -1)?Math.min(indexLeft, indexRight):((indexLeft == -1)?indexRight:indexLeft);
}
Here's solution in python:
def getIndexOf(arr, y):
i =0
arr.sort()
while(i <= len(arr)):
if(y in arr):
indices = [i for i, x in enumerate(arr) if x == y]
print("Start Index :", min (indices),"End Index :",max(indices))
break
else:
print("Not in list")
print("Start Index :", -1 ,"End Index :",-1 )
break
return
arr = [0,2,3,3,3,10,10]
y = 6
getIndexOf(arr,y)
Use binary search to locate a given number in that number sequence. From that location, proceed both to the right and to the left until you see different numbers and mark the boundaries.
If the binary search is unable to find the given number, return -1,-1
I don't have the specifics right off the top of my head, but you'll want to do a modified binary search again once you are in the range. Searching linearly in each direction as you state should, if I am not mistaken, result in O(n) overall runtime, not the Sub O(n) the answer sought.
not required,i guess...suppose you found any one position of required value x in array using bsearch say k
now use this modified binary search in left side
low=0;high=k-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==x)
high=mid-1;
else low=mid+1
}
after this loop,the index value low will contain the first occurrence of x in array.
similarly you can search in other part for last occurrence too
Python:
If i can use inbuilt functions, below one would help answer your question?
def getindices(tlist, n):
indices = [-1,-1]
if tlist.count(n):
indices = map(lambda i: tlist.index(i[1], i[0]), \
enumerate([n] * tlist.count(n), tlist.index(n)))
indices = [indices[0], indices[-1]]
return indices
Testing:
>>> getindices([1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5], 4)
[8, 11]
>>> getindices([1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5], 11)
[-1, -1]
>>>
void search(int k, int start, int end, int &left, int &right, int a[])
{
if (start <= end)
{
int mid = end - ((end-start)>>1);
if(a[mid] == k)
{
if (left > mid) left = mid;
if (right < mid) right = mid;
search(k, start, mid-1, left, right, a);
search(k, mid+1, end, left, right, a);
}
else if (a[mid] < k)
search(k, mid+1, end, left, right, a);
else
search(k, start, mid-1, left, right, a);
}
return;
}
public class ReturnIdx {
public static void main(String[] args) {
int arr[] = {-1, 0, 0, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6};
startAndEnd(arr,2);
}
private static void startAndEnd(int[] arr, int num) {
int stidx =getPos(arr,num);
int start = stidx;
if(stidx != -1){
int end = arr.length;
int mid;
while(start<=end){
mid = (start+end)/2;
if(arr[mid] < num){
start = mid+1;
}else if(arr[mid] > num){
end = mid - 1;
}
else {
if(start == end)
break;
else{
start = mid;
}
}
}
System.out.println("start: "+stidx+" end: "+end);
}
else{
System.out.println("The element does not exist");
}
}
static int getPos(int[] arr, int num) {
int start = 0;
int end = arr.length-1;
int mid;
while(start<=end){
mid = (start+end)/2;
if(arr[mid] < num){
start = mid+1;
}else if(arr[mid] > num){
end = mid - 1;
}
else {
if(start == end)
return start;
else{
end = mid;
}
}
}
return -1;
}
//Here is the simple solution in java.
public static void getStartEndIndex(int[] arr, int number) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == number) {
startIndex = i;
int j = i;
do {
j++;
} while (arr[j] == number);
endIndex = j - 1;
System.out
.println("Start and End Index of the given number is :"
+ startIndex + " and " + endIndex);
break;
}
}
}
This is an O(n) solution and the problem explicitly requires "Complexity should be less than O(n)".
Guaranteeing an O(n) solution is not possible, since you would need to iterate over all elements at least once in the case where the target value has no corresponding element present in the array.
I meant to say "[Guaranteeing less than O(n) complexity in the] solution...", as opposed to "[Guaranteeing an O(n)] solution..."
The binary search will work like like this:
a. First find the start index of the number
b. Then find its end index
c. Thus we have find the start and the end index
- vgeek July 12, 2013#include <stdio.h> #include <conio.h> int firstIndex(int arr[],int low,int high,int key,int n) { if(high>=low) { int mid=low+(high-low)/2; if((mid==0||key>arr[mid-1])&&arr[mid]==key) return mid; else if(arr[mid]<key) return firstIndex(arr,mid+1,high,key,n); else return firstIndex(arr,low,mid-1,key,n); } return -1; } int lastIndex(int arr[],int low,int high,int key,int n) { if(high>=low) { int mid=low+(high-low)/2; if( ( mid == n-1 || key < arr[mid+1]) && arr[mid] == key ) return mid; else if(key < arr[mid]) return lastIndex(arr, low, (mid -1), key, n); else return lastIndex(arr, (mid + 1), high, key, n); } return -1; } int main() { int arr[]={1,2,2,2,3}; int n=sizeof(arr)/sizeof(arr[0]); int fi=firstIndex(arr,0,n-1,2,n); int si=lastIndex(arr,fi,n-1,2,n); printf(" The first and last indices are %d %d ",fi,si); }