How to get the last char in an array with a binary search

Question

My teacher wrote an algorithm to find a number in an array. I have tried to convert it to find a char.

If I search for the the first char of an array it works, but if I try to find the last char in the same array it gives me 0 or an unexpected number (like 100+, when the array is like 4 chars).

Here's the code:

int myIndex = binarySearch(sentence , word[0], 0, sentence.length -1);

char [] sentence = {'s','t','a','c','k','o','v','e','r','f','l','o','w'};
char [] word = {'o','v','e','r'};

static int binarySearch(char [] arr, char x, int l, int r){
    if(r<l){
        return 0;
    }

    int m = l+(r-l)/2;
    if(arr[m] == x){
        return m;
    }
    if(arr[m] < x){
        return binarySearch(arr, x, m+1, r);
    }
    return binarySearch(arr, x, l, m-1);
}

If I search for the first letter in the word array it works fine, but if I search for the last letter in the word array it breaks.

Binary search only works on sorted arrays but your sentence array is not sorted at all. — user6073886
– user6073886, Commented Jun 12, 2019 at 10:50
in addigion, correct binary search algo must work fine with last or first place in array — user8426627
– user8426627, Commented Jun 12, 2019 at 11:03

Dejan · Accepted Answer · 2019-06-12 10:50:05Z

1

You are using a binary search on the input array arr of chars which is not sorted. So, you must first sort the array or use a linear search on the unsorted array.

answered Jun 12, 2019 at 10:50

Dejan

1,0281 gold badge10 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Shrey Garg · Accepted Answer · 2019-06-12 10:53:00Z

0

You need to have a sorted array to do a binary search.

For this,

add this line before you call search method : Arrays.sort(sentence);

answered Jun 12, 2019 at 10:53

Shrey Garg

1,3371 gold badge8 silver badges17 bronze badges

Comments

Mak · Accepted Answer · 2019-06-12 10:54:56Z

0

This will work without sorting array. Can you please try with this,

 int myIndex = binarySearch(sentence , 'w');



 static int binarySearch(char[] arr, char x) 
     { 
         int l = 0, r = arr.length - 1; 
         while (l <= r) { 
             int m = l + (r - l) / 2; 

             int res = String.valueOf(x).compareTo(String.valueOf(arr[m])); 

             // Check if x is present at mid 
             if (res == 0) 
                 return m; 

             // If x greater, ignore left half 
             if (res > 0) 
                 l = m + 1; 

             // If x is smaller, ignore right half 
             else
                 r = m - 1; 
         } 

         return -1; 
     }

answered Jun 12, 2019 at 10:54

Mak

1,0768 silver badges20 bronze badges

Comments

Zhivar Sourati · Accepted Answer · 2019-06-12 10:57:47Z

0

binary search that you are using only works on sorted arrays , besides this point your code is correct

you should sort the array first of all like this : (by importing the java arrays)

import java.util.Arrays; 

Arrays.sort(array_of_chars);

edited Jun 12, 2019 at 10:57

answered Jun 12, 2019 at 10:54

Zhivar Sourati

6138 silver badges10 bronze badges

1 Comment

baao Over a year ago

That's not java

n0noob · Accepted Answer · 2019-06-12 16:20:53Z

0

For binary search to work, please sort the array first.

//import utility class
import java.util.Arrays;

//Make use of sort function to sort the array
Arrays.sort(sentence);

//Call binary search now
int myIndex = binarySearch(sentence , word[0], 0, sentence.length -1);

answered Jun 12, 2019 at 16:20

n0noob

9491 gold badge9 silver badges24 bronze badges

Collectives™ on Stack Overflow

How to get the last char in an array with a binary search

5 Answers 5

Comments

Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related