Бинарный(двоичный) поиск

216

20 июля 2018, 00:10

Пишу домашку, нужно написать поиск, который будет выбирать границы и искать в той части массива, что может идти не так в моём коде?

package javaguru;
import java.util.Scanner;
import java.util.Random;
public class hw {
public static void main(String[] args) {
    int[] nums = {3, 7, 19, 49, 54, 98, 105, 207, 209, 382};

    int i = 0, poisk = 7;

    int n = nums.length;
    int left = 0, right = nums.length, mid;
    mid = (left + right)/2;
}
    while(nums[mid]!= poisk){
            if (nums[mid] == poisk) {
                System.out.println("Chislo najdenno"+poisk);
                break;
            } else if (nums[mid] < poisk) {
                right = mid+1;
            } else if (nums[mid] > poisk) {
                left = mid - 1;
            }
        }
    }
}

Подправлил код, вот что из этого вышло, но всё равно результат не тот

package javaguru;

import java.util.Scanner; import java.util.Random;

public class hw {

public static void main(String[] args) {
    int[] nums = {3, 7, 19, 49, 54, 98, 105, 207, 209, 382};

    int i = 0, poisk = 207;

    int n = nums.length;
    int left = 0, right = nums.length - 1, mid;


    while(left <= right){
        mid = (left + right)/2;
        if (nums[mid] == poisk) {
                System.out.println("Chislo najdenno"+poisk);
                break;
            } else if (nums[mid] < poisk) {
                right = mid-1;
            System.out.println(nums[mid]);
            } else if (nums[mid] > poisk) {
                left = mid + 1;
            System.out.println(nums[mid]);
        }
       }
}

}

Answer 1

В условии while сравнивай не значение, а индексы left, right

Задание правой границы right = nums.length в данном случае неправильно, уменьши её на 1.

В последнем исправлении ты напутал с половинками. Неужели этого по выводу не видно? Вот рабочий код:

public class HelloWorld
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    int[] nums = {3, 7, 19, 49, 54, 98, 105, 207, 209, 382};

    int i = 0, poisk = 49;
    int n = nums.length;
    int left = 0, right = nums.length - 1, mid;
    System.out.println("Ischem " + poisk);
    while(left <= right){
        mid = (left + right)/2;
        if (nums[mid] == poisk) {
                System.out.println("Chislo najdeno "+poisk);
                break;
            } else if (nums[mid] > poisk) {
                right = mid-1;
            System.out.println(nums[mid]);
            } else if (nums[mid] < poisk) {
                left = mid + 1;
            System.out.println(nums[mid]);
        }
    }

  }
}