Binary search algorithm check if an integer is contained in an array

Question

I am having trouble implementing binary search within my code, can you explain how it works.

binarySearch takes an array of integers a and an integer n and uses binary search algorithm check if n is contained in a. it returns true if n is contained in a, as well as printing the number of decision made and false otherwise.

import java.util.Arrays;
import java.util.Random;

public class Excersice2 {

    public static void main(String[] args) {
        int[] arr = createArray(10);
        System.out.println("the array not sorted");
        printArray(arr);
        arr = sortArray(arr);
        System.out.println("the array sorted");
        printArray(arr);
        System.out.println(binarySearch(arr,50));

    }

    public static void printArray(int []arr)
    {

        System.out.println(Arrays.toString(arr));

    }

    public static int [] createArray(int n) {
        int[] arr = new int[n];

        Random rand = new Random();
        for(int i = 0; i < n; i++) 
            arr[i] = rand.nextInt(101);

        return arr; 

    }

    public static int[] sortArray(int[] arr) {
        Arrays.sort(arr);
        return arr;

    }

    public static boolean binarySearch(int arr[], int n) {
        int firstIdx = 0;
        int lastIdx = - 1;
        int middle = (firstIdx + lastIdx)/2;
        int idx = arr.length/2;

        while( firstIdx <= lastIdx) {
            if(binarySearch[middle] < arr);

        }


    }

}

The outcomes should look: It took 2 times to find that the value 50 is contained the array. When looking through the list

Tip: Do not generate random test cases when you are first writing a solution, as you have here: rand.nextInt. You want to be able to run it in a reproducible way to prove to yourself that you're making progress and fixing bugs. By introducing randomness before you're even confident in your solution, you're making the entire thing much harder for yourself. It also means that we will never be able to reproduce the exact problems that you're experiencing. — Michael
– Michael, Commented Nov 20, 2018 at 11:22
Tip #2: But you can get reproducible "random" numbers if you initialize Random with a fixed seed; see the javadocs. — Stephen C
– Stephen C, Commented Nov 20, 2018 at 11:41
For an explanation of Binary Search, read en.wikipedia.org/wiki/Binary_search_algorithm. (I was going to suggest Rubber Duck debugging. Then I realized that you haven't finished coding the binarySearch method. You can't debug it unless you have coded it.) — Stephen C
– Stephen C, Commented Nov 20, 2018 at 11:44

unarr · Accepted Answer · 2018-11-20 12:41:33Z

You can use Binary Search Algorith when you have an array of numbers and your array is sorted. Algorithm checks if the key (the number you are looking for) is equal with the middle value of the array. If it is, the searching is done and the key is at the middle position. If it isnt, then the algorithm checks if the key is greater or less than the middle value. if it is greater, then the algorithm repeats the search only at the second half of the array, taking as left the next position of the middle. If it is less, then only at the first half taking as right the position before the middle. And repeats that until the key is found or there is no more positions in array.

Calling the binary search method

//the number you are looking for. For example 4.
int key = 4;
//the first element of array
int left = 0;
//the last element of array
int right = arr.length - 1;
int pos = binarySearch(left, right, key);
if(pos == -1) { System.out.println("Array does not contain key"); }
else { System.out.println("Array contains key at position : " + pos); }

Binary Search Algorithm method

int binarySearch(int left, int right, int key) {

        int pos;
        int mid;

        if(left > right) {
            //there is no more positions to search
            pos = -1;
        } else {
            //Getting the middle position of array
            mid = (left + right) / 2;
            //if the key is the middle positions value
            if(arr[mid] == key)
                pos = mid;
            //if the key is less than the middle value
            else if(key < arr[mid])
                //repeat the search only at the first half of array
                pos = binarySearch(left, mid-1, key);
            else
                //else if the key is greater than the middle value
                //search at the second half of array
                pos = binarySearch(mid+1, right, key);
        }
        return pos; 
    }

Collectives™ on Stack Overflow

Binary search algorithm check if an integer is contained in an array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related