CODEWITHSUNDEEP
javabinary-search
Hana Uddin
Hana Uddin

Reputation: 13

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

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

Upvotes: 0

Views: 2960

Answers (1)

unarr
unarr

Reputation: 86

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

Upvotes: 3

Related Questions