Algorithm | Binary Search

Binary Search

Binary search is a method for finding a specific value in an ascending sorted list by first choosing the middle value and comparing whether it is larger or smaller than the target value.

Advantage: each repeated search doubles the probability of finding the target value, so it is fast.
Disadvantage: it can only be used on sorted lists.

Method Using a Loop

package com.devkuma.algorithum.programming.search.binary;

public class BinarySearchWhile {

    int search(int[] nums, int target) {
        int startIndex = 0;
        int endIndex = nums.length - 1;

        int middle = 1;

        while (startIndex <= endIndex) {
            middle = (startIndex + endIndex) / 2;
            if (nums[middle] == target)
                return middle + 1;
            else if (nums[middle] > target)
                endIndex = middle - 1;
            else
                startIndex = middle + 1;
        }
        return middle;
    }

    public static void main(String[] args) {
        BinarySearchWhile search = new BinarySearchWhile();

        int[] nums = {15, 28, 65, 67, 88, 92, 100, 150};
        int target = 28;
        int index = search.search(nums, target);

        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }
}

Execution result:

5은 2번째 있습니다.

Method Using Recursion

package com.devkuma.algorithum.programming.search.binary;

public class BinarySearchRecursion {

    int search(int arr[], int target, int startIndex, int endIndex) {
        if (startIndex > endIndex)
            return -1;

        int middle = (startIndex + endIndex) / 2;
        if (arr[middle] == target)
            return middle;
        else if (arr[middle] > target)
            return search(arr, target, startIndex, middle - 1);
        else
            return search(arr, target, middle + 1, endIndex);
    }

    public static void main(String[] args) {
        BinarySearchRecursion search = new BinarySearchRecursion();

        int[] nums = {15, 28, 65, 67, 88, 92, 100, 150};
        int target = 28;
        int startIndex = 0;
        int endIndex = nums.length - 1;

        int index = search.search(nums, target, startIndex, endIndex);

        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }
}

Execution result:

28은 2번째 있습니다.

Binary Search Example Explanation

Using the array from the example above, the binary search for 28 can be written out as follows.

{ 15, 28, 65, 67, 88, 92, 100, 150 }
- Middle value: 88 -> smaller -> { 15, 28, 65, 67 }
- Middle value: 43 -> smaller -> { 15, 28 }
- Middle value: 28 -> end