二进制搜索字符串中的一个字符 - 的Java [英] Binary Search for a char in a string - Java

问题描述

我试图做我的作业。我想，我真的很接近解决，但我不能这样做。我一直在试图做到这一点，去年几个小时。

我所试图做的事：我有一个字符串和一个char。我想实现二进制搜索，寻找一个字符，但它不返回我想要的价值。那么它是正确的，但我想这code返回5，而不是4。

这是我的code，你可以帮我解决呢？没有排序的方法，因为我不想在这里code是超级长，但请假定排序方法正确排序。如果您想看到的排序方法，那么我能为您上传

我想AP preciate任何形式的帮助，因为我已经花了办法不多的时候呢..：/

。

 公共静态无效的主要（字串[] args）{
         字符串s =ABCDEFG;
         焦C ='E';
      的System.out.println（findRecursiveD（S，C））;     }     公共静态INT的binarySearch（的char []一，焦炭C中，int开始，诠释完）{      INT中旬=（START +前端）/ 2;
      如果（A [MID] == C）
          返回中旬;
      否则如果（一个[MID] c为C）
          返回的binarySearch（A，C，中+ 1，结束）;      其他
       返回的binarySearch（A，C，启动，中旬）;
     }     公共静态INT findRecursiveD（字符串s字符C）{
      INT开始= 0;
      字符串s = S + C;
      的char [] B = S.toCharArray（）;
      INT结束= b.length个;
      排序（B，0，结束）;
      字符串A =新的String（B）;
      的System.out.println（A）;
      返回的binarySearch（B，C，起点，终点）;
     }
    }
 

解决方案

使用这样的：

 的System.out.println（findRecursiveD（S，C）+ 1）;
 

您需要添加一个，因为字符串中的第五位是位置4.第一个位置INT EH字符串编号为0 4是正确答案，如果你想要的位置的编号。但是，如果你要计算从1开始，那么你需要添加一个。

此外，您还需要终止搜索时开始==结束。你会遇到不好的问题，是启动+ 1大于end，所以你应该测试，并避免出现这种情况。开始时结束==，再经过验证字符在位置中旬（== ==开始结束）不是C，那么检查此条件，并返回一些特别的东西，比如-1，或抛出异常。

 公共静态INT的binarySearch（的char []一，焦炭C中，int开始，诠释完）{  INT中旬=（START +前端）/ 2;
  如果（A [MID] == C）{
      //现在要查找该值的'最后'字符
      而（中间±1℃;则为a.length＆放大器;＆放大器;一个[中间+ 1] ==三）{
          中期++;
      }
      返回中旬;
  }
  否则，如果（开始==结束）{
      //如果没有该值的字符发现
      返回-1;
  }
  否则如果（一个[MID] c为C）{
      返回的binarySearch（A，C，中+ 1，结束）;
  }
  其他{
      返回的binarySearch（A，C，启动，中旬）;
  }
}
 

和删除，增加了一个字符到被搜索的字符串的声明。我不明白为什么在增值的那架空帮助，它似乎是一个不好的编码实践中学习，反正你搜索之前修改搜索数据。

I am trying to do my assignment. I think that I am really close to solving it, but I can't do it.. I've been trying to do it for last several hours.

What I am trying to do: I have a string and a char. I am trying to implement the binary search to look for a char, but it doesn't return the value that I want. Well it is correct, but I want this code to return 5 instead of 4.

This is my code, can You help me to solve it? There is no sort method, because I didn't want the code in here to be super long, but please assume that sorting method sorts correctly. If you'd like to see the sorting method then I am able to upload it for you.

I would appreciate any kind of help, because I've spent way to much time for it.. :/.

     public static void main(String[] args) {
         String s = "abcdefg";
         char c = 'e';
      System.out.println(findRecursiveD(s, c));

     }

     public static int binarySearch(char[] a, char c, int start, int end) {

      int mid = (start + end) / 2;
      if(a[mid] == c) 
          return mid;
      else if (a[mid] < c)
          return binarySearch(a, c, mid+1, end);

      else
       return binarySearch(a, c, start, mid);
     }

     public static int findRecursiveD(String s, char c) {
      int start = 0;
      String S = s + c;
      char[] b = S.toCharArray();
      int end = b.length;
      sort(b, 0, end);
      String A = new String(b);
      System.out.println(A);
      return binarySearch(b, c, start, end);
     }
    }

解决方案

USe this:

System.out.println(findRecursiveD(s, c) + 1);

You need to add one, because the 5th position in the string is position 4. The first position int eh string is numbered 0. 4 is the correct answer if you want the number of the position. But if you want to count starting with 1, then you need to add one.

Also, you need to terminate searching when start == end. You will run into bad problems is start+1 is greater than end, so you should test for, and avoid this situation. When start == end, then after to verify that the character at position mid (== start == end) is not c, then check for this condition and return something special, like -1, or throw an exception.

public static int binarySearch(char[] a, char c, int start, int end) {

  int mid = (start + end) / 2;
  if(a[mid] == c) {
      //now search for the 'last' character of that value
      while (mid+1<a.length && a[mid+1]==c) {
          mid++;
      }
      return mid;
  }
  else if (start==end) {
      //if no character of that value found
      return -1;
  }
  else if (a[mid] < c) {
      return binarySearch(a, c, mid+1, end);
  }
  else {
      return binarySearch(a, c, start, mid);
  }
}

And remove the statement that adds a character into the string being searched. I don't see why that overhead of adding in a value helps, and it seems like a bad coding practice to learn anyway to modify the search data before you search it.

这篇关于二进制搜索字符串中的一个字符 - 的Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！