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).
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.
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.
However, there are four ways to write this sentence programmatically, so I would like to introduce this.
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.
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
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.
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;
}
}
Recommended Posts