search.sol

// SPDX-License-Identifier: GPL-3.0
pragma solidity ^0.8.1;

contract SortedSequence {
    uint256[100]             public _array;
    mapping(uint256 => bool) public _mapping;
    
    function setValue(uint256[100] calldata init_seq) public {
        for(uint8 i = 0; i < 100; i++) {
            _array[i] = init_seq[i];
            _mapping[init_seq[i]] = true;
        }
    }
}

contract BadSearch is SortedSequence {
    function linSearch(uint256 target) public view returns (bool) {
        for(uint256 i; i < _array.length; i++) {
            if(_array[i] == target)
                return true;
        }
        return false;
    }
    
    function binSearch(uint256 target) public view returns (bool) {
        uint256 L;
        uint256 H = _array.length - 1;
        uint256 M;
        
        if(_array[0] > target)
            return false;
        
        while(L <= H) {
            M = (L + H) / 2;
            
            if(_array[M] == target)
                return true;
            else if(_array[M] < target) 
                L = M + 1;
            else // _array[M] > target
                H = M - 1;
        }
        
        return false;
    }
}

contract OkaySearch is SortedSequence {
    function askMapping(uint256 target) public view returns (bool) {
        return _mapping[target];
    }
}