二分探索

*目的のデータを探すアルゴリズムを学ぶ vue.jsの勉強を書籍使ってしていたところ、使っているノートPCのキーの反応がまったくなく修理に... サンプルアプリは完成して落ち着いたので、苦手だったアルゴリズムの勉強を少しずつ進めていきたい。 探索アルゴリズムとは任意の数〇個のデータ（配列の）中から目的の値を探すアルゴリズム。 rubyを使って学んでいきます。今回は探索アルゴリズムの中から基本の線形探索と二分探索について書いていく。*線形探索（リニアサーチ）array = [14,32,45,67,89,122] 例えば89という目的の数字を探したいアルゴリズム 目的のデータがどこにあるか？配列…

paizaラーニングの新・アルゴリズムとデータ構造入門 Java編に「新・アルゴリズムとデータ構造入門 Java編9: 二分探索」が追加されました。新・アルゴリズムとデータ構造入門 Java編では、初心者でも動画レッスンと演習問題を通して、線形探索やO記法、ソートなどのアルゴリズムが学べます。今回は、新・アルゴリズムとデータ構造入門 Java編9: 二分探索の内容をご紹介します。paizaラーニングについて詳しくはこちら 二分探索について 新・アルゴリズムとデータ構造入門 Java編に追加されたレッスンの内容 新・アルゴリズムとデータ構造入門 Java編9: 二分探索 01:二分探索 02:x…

atcoder.jp・参考： ABC312 C問題（Invisible Hand）を解く - プロひろ・説明：二分探索で解く。okとngを二分探索で更新していきokが最終結果になる。( 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita を参照) import bisect n,m=map(int, input().split()) a=list(map(int, input().split())) b=list(map(int, input().split())) a.sort() b.sort() ok=10**9+1 ng=0 while abs(ok-ng…

atcoder.jp・考え方：二分探索で解ける。まず、setにして重複を消す。次に反転文字列が文字列全体にないか、二分探索してあったら答えを-1する。 import bisect n=int(input()) s=[] for _ in range(n): s.append(input()) s=list(set(s)) #setで重複を消す ns=len(s) s.sort() for i in range(len(s)): #先頭を消す。自分自身を参照しないため。 p=s.pop(0) #p[::-1]でpの反転文字 l=bisect.bisect_left(s,p[::-1]) r=bi…

概要 データ探索アルゴリズムの1つ。探索対象はソート済みのデータ群。探索範囲を半分に絞り込む作業を繰り返す。 半分に絞り込む作業 ①探索範囲の中心の値を比較する。②探索対象より大きい場合は中心より左に存在する。③探索対象より小さい場合は中心より右に存在する。以下の図の黄背景は3、赤背景は12を探した場合のイメージ図 public static int Exec(List<int> numbers, int target) { var left = 0;// 紫文字 var right = numbers.Count - 1;// 赤文字 while() { var half = left + …

atcoder.jp・参考： Submission #42147989 - KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305） ・考え方：前処理をしてクエリの中の処理を軽くする。二分探索を使うのでスライスにおけるAのi番目までの睡眠時間を前処理として行えば良い。プログラムの処理1では二分探索の位置が偶数だとansを引きすぎたり足しすぎたりしているのでそれを処理する。・実装例： import bisect n=int(input()) a=list(map(int,input().split())) #前処理。 #aに対応…

・問題： atcoder.jp ・参考： https://atcoder.jp/contests/abc304/submissions/41948730 https://atcoder.jp/contests/abc304/submissions/41961121 ・説明 a,bの線でケーキを切るのでa,bの格子(切り分けられたケーキ)の中でいちごの位置を二分探索してそれをtにいれる。 c(辞書型で{key、value}と1つの要素に2つの値を持つ)を作ってcのkeyにtがすでにあったらc[t](cのvalue)に++、それ以外はc[t]=1 cのvalue(場所毎のいちごの数)のうち最大、最…