# 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 || 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++) {
}
}
};
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

• Use loops rather than recursion
• Array operations are heavy, so use indexes