[GO] A story about writing a binary search method at an in-house study session

Introduction

This time, I tried to write the task of writing a search program by the binary search method together with young employees. Regarding online search, it was OK under the restriction that the answer itself is not checked (copy and paste / copying is prohibited).


problem

An arbitrary value B is extracted by a binary search from an array A in which numerical values from 1 to 1000 are stored in order.


solution

Since it is assumed that the binary search method will be used this time, everyone will write the program with the same policy. The procedure of the binary search method is as follows.

  1. Take the value stored in the center of the array and compare it with the desired value
  2. Return if the desired value
  3. If it is larger than the target value, the next search target is before the center (returns to 1).
  4. If it is smaller than the target value, the next search target is after the center (returns to 1).

However, there are four ways to write this sentence programmatically, so I would like to introduce this.


Recursive or loop

This time too, these two types of writing came out first. Please refer to the basic policy as it is the same as the previous article.

A story about writing a ratio calculation at an in-house study session

However, since this time the search is from an array, I think that the upper limit of the number of data in the array is not necessarily set when actually using it. If you want to use it in a real project, it is safer to use a loop.


Postscript

It was also necessary to pay attention to the overflow due to the index calculation method pointed out in the comment.

[Wikipedia-Binary Search-Implementation Mistakes](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2#% E5% AE% 9F% E8% A3% 85% E4% B8% 8A% E3% 81% AE% E9% 96% 93% E9% 81% 95% E3% 81% 84)

I made a mistake in the above link that you posted in the comment. There is a risk of overflow if you simply add the indexes, so use subtraction to avoid the overflow.

Positive

lower + (upper - lower) / 2

Wrong

(upper + lower) / 2

Array manipulation or index

These two methods have emerged as ways to proceed with the search. Since it is difficult to explain in letters, I will post the code.

Array manipulation.kt


    var centerVal: Int = 0
    do{
        val center: Int = list.size / 2
        centerVal = list.get(center)

        list = if(centerVal > target) {
            list.dropLast(center)
        }else {
            list.drop(center)
        }
    }while(centerVal != target)
    return centerVal

index.kt


    var centerVal: Int = 0
    do{
        val center: Int = (start + end) / 2
        centerVal = list.get(center)

        if(centerVal > target) {
            end = center
            continue
        }
        start = center
    }while(centerVal != target)
    return centerVal

Is it like this for each? Depending on the while condition, it does not have to be do-while. There is not much difference in appearance, and it seems that you like it, but array operations are heavy processing and should be avoided.


Code example

The following is the code that rewrites this problem so that it is easy to compare what was written in each language. As mentioned above, we are using the array index and looping around. This time there were no Swift participants, so Swift is closed.


Kotlin

fun main(args: Array<String>) {
    val A = List<Int>(1000, { it + 1 })
    val B = 233
    println(binarySearch(A, B))
}

fun binarySearch(list: List<Int>, target: Int): Int{
    if(target < list.first() || list.last() < target) {
        return -1
    }
    
    var first = 0
    var last = list.size

    while(first + 1 != last) {
        val center = first + (last - first) / 2
        val centerVal = list.get(center)

        if(centerVal == target) {
            return centerVal
        }
        
        if(centerVal < target) {
            first = center
        }else {
            last = center
        }
    }

    return -1
}

PHP

<?php

function main() {
    $A = range(1, 1000);
    $B = 233;

    echo binarySearch($A, $B);
}

function binarySearch($list, $target)
{
    if ($target < $list[0] || end($list) < $target) {
        return -1;
    }

    $first = 0;
    $last = count($list);

    while($first + 1 !== $last) {
        $center = floor($first + ($last - $first) / 2);
        $centerVal = $list[$center];

        if($centerVal === $target) {
            return $centerVal;
        }

        if($centerVal < $target) {
            $first = $center;
        }else {
            $last = $center;
        }
    }

    return -1;
}

main();

JavaScript

const main = () => {
  const A = new Array(1000)
    .fill('a')
    .map((el, i) => i + 1)
  const B = 233

  console.log(binarySearch(A, B))
}

const binarySearch = (list, target) => {
  let first = 0
  let last = list.length

  if(target < list[first] ||list[last-1] < target) {
      return -1
  }

  while (first + 1 !== last) {
    const center = Math.floor(first + (last - first) / 2)
    const centerVal = list[center]

    if (centerVal === target) {
      return centerVal
    }

    if (centerVal < target) {
      first = center
    } else {
      last = center
    }
  }

  return -1
}

main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        List<Integer> A = new ArrayList<Integer>()        {
            {
                for(int i = 1; i <= 1000; i++) {
                    add(i);
                }
            }
        };
        int B = 233;

        System.out.println(binarySearch(A, B));
    }

    private static int binarySearch(List<Integer> list, int target) {
        int first = 0;
        int last = list.size();

        if(target < list.get(first) ||list.get(last - 1) < target) {
            return -1;
        }

        while (first + 1 != last) {
            final int center = (int) Math.floor(first + (last - first) / 2);
            final int centerVal = list.get(center);

            if (centerVal == target) {
                return centerVal;
            }

            if (centerVal < target) {
                first = center;
            } else {
                last = center;
            }
        }

        return -1;
    }    
}

Summary

Recommended Posts

A story about writing a binary search method at an in-house study session
A story about writing a ratio calculation at an in-house study session
A story about young people's design skills improving at a 15-minute study session every morning
A story about how young people's behavior improved surprisingly at a 15-minute study session every morning
Binary search binary search method
Arbitrary search method in an array using binary search
Binary search method
A story about going to a Docker + k8s study session [JAZUG Women's Club x Java Women's Club]
[Java] A story about IntelliJ IDEA teaching Map's putIfAbsent method
Practice of binary search method