CODEWITHSUNDEEP
javaarraysrecursion
Sufferring
Sufferring

Reputation: 49

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

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.

Upvotes: 0

Views: 88

Answers (5)

n0noob
n0noob

Reputation: 939

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);

Upvotes: 0

Zhivar Sourati
Zhivar Sourati

Reputation: 593

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);

Upvotes: 0

Mak
Mak

Reputation: 1078

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; 
     }

Upvotes: 0

Shrey Garg
Shrey Garg

Reputation: 1337

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);

Upvotes: 0

Dejan
Dejan

Reputation: 1028

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.

Upvotes: 1

Related Questions