二分探索の雛形

_binary_search.md

二分探索の雛形

二分探索のコーディング例を各言語で。
配列（スライス等もある）はint型で表現。
※ジェネリクスを利用している言語もあります。

binary_search.cs

// test => https://dotnetfiddle.net/5R7VUM

public class SearchResult {
    public int Position;
    
    public bool IsExists;
	
    public SearchResult() {
        Position = -1;
        IsExists = false;
    }
    
    public SearchResult(int Position, bool IsExists) {
        this.Position = Position;
        this.IsExists = IsExists;
    }
}

public class Main
{
    public SearchResult BinarySearch<T>(IList<T> data, T value)
        where T : IComparable
    {
        int left  = 0;
        int right = data.Count - 1;

        while (left <= right)
        {
            int mid = (left + right) / 2;

            if (data[mid].CompareTo(value) == 0)
            {
                return new SearchResult(mid, true);
            }
            else if (data[mid].CompareTo(value) < 0)
            {
                left = mid + 1;
            }
            else if (data[mid].CompareTo(value) > 0)
            {
                right = mid - 1;
            }
        }

        return new SearchResult(right + 1, false);
    }
}

binary_search.go

// test => https://go.dev/play/p/XgcXlEfDoeQ

// constraints.Ordered と同じ定義
type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
	~float32 | ~float64 | ~string
}

func binarySearch[T Ordered](data []T, value T) (int, bool) {
	left  := 0
	right := len(data) - 1

	for left <= right {
		mid := (left + right) / 2

		if data[mid] == value {
			return mid, true

		} else if data[mid] < value {
			left = mid + 1

		} else if data[mid] > value {
			right = mid - 1
		}
	}

	return right + 1, false
}

binary_search.py

def binary_search(data, value):
    left = 0
    right = len(data) - 1

    while left <= right:
        mid = (left + right) // 2

        if data[mid] == value:
            return (mid, True)

        elif data[mid] < value:
            left = mid + 1

        elif data[mid] > value:
            right = mid - 1

    return (right + 1, False)

binary_search.rs

// test => https://play.rust-lang.org/?version=stable&mode=release&edition=2021&gist=3d060b20d2985851a406252734e8ffd7

fn binary_search<T>(data: Vec<T>, value: T) -> (usize, bool)
    where T: std::cmp::PartialOrd
{
    if data.capacity() == 0 || data.len() == 0 {
        return (0, false)
    }
    
    let mut left  = 0;
    let mut right = data.len() - 1;
    
    while left <= right {
        let mid = (left + right) / 2;
        
        if data[mid] == value {
            return (mid, true);
            
        } else if data[mid] < value {
            left = mid + 1;
            
        } else if data[mid] > value {
            if mid == 0 {
                return (0, false)
            }
            
            right = mid - 1;
        }
    }
    
    return (right + 1, false);
}

binary_search.ts

// https://www.typescriptlang.org/play?#code/DYUwLgBAlmILYGcIF4IG0BMAaCBmHArDgOw4CMZ5+EZpNAnDhtRo3pXnQCwdfVd0C1AmwBsHUXWIdi1YmwAc1BW3rEAugG4AUKEgAnEAjIAudADsArnABGIfThsB7J6ACG59Sgg2o5t-oAngDKIAEAxgAWABQw8AhMuACUOnoQhggYZmhWtvaOLu6e3r7+QaERMXGIOFyiKdra4U7mCK4gAHTATgDm0QAGgEXGgES+gOoMgPoMgA6mgFj-zCgAfBCAlgyAygyA+P-TACQA3hlkaAAM6gC+gFaugHduOIAa2oAU6lu7RvtkJ-0Nza3tXb0DIxMzdQtlut7hkMIcThdrncdqC0M9jq8dNoAGaWczhMBQFo+PwBEJhfRRaIAEzcYDcZlydn0aHUOAAbm5gJYQJTrNSktkqfkfIUwsVttoIMKIGlQMjIN4DjoRaLwOkoD1IpBUKTyV0QOYemBIhAALQ0JGygDukSgoAg0XFkAAPKh9IrlUkIILZbK0nAoMTvABZMmRDrI7pOfTRK0gCUQADUCqVYGdAHoIBgGkK3cKoMjLWq3GhPcSvMhUIzmSBna7027DGBLPpzOh8zgwPoWVpGpWIMcICBgAgQNAsySybn814bRASyzy2mO8Lrd589HDe3K12e32B9nh3mvV5FpOyy6Z7OHXGF179cuO8djzfj9Xa-W0KflUuOMimX228cgA

function binarySearch(data: number[], value: number): [number, boolean] {
    let left  = 0;
    let right = data.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (data[mid] == value) {
            return [mid, true];

        } else if (data[mid] < value) {
            left = mid + 1;

        } else if (data[mid] > value) {
            right = mid - 1;
        }
    }

    return [right + 1, false];
}