二分探索のまとめ

二分法の主な詳細は、左右の間隔の選択にあります。 leetcode704のように。

[704] バイナリサーチ

var search = function(nums, target) {
 let start = 0;
 let end = nums.length - 1;
 while(start <= end){
 let mid = start + Math.floor((end - start)/2);
 let midVal = nums[mid];
 if(target === midVal) return mid;
 if(target < midVal){
 end = mid - 1;
 }else{
 start = mid + 1;
 };
 };
 return -1;
};

ポイントは、見るべき間隔を明確にすることです。ここでは、閉鎖前と閉鎖後を示します。

左境界検索

値を見つけるための基本的なソートされた非繰り返し配列に加えて、左右の境界の値を見つけるためのソートされた繰り返し配列のようなものがあります。例えば、[1,2,3,3,3,3,4,5] という配列のように、 3 という値が与えられたときに、その配列の中で 3 という値が最初に現れる場所を探します。この種の検索は左境界検索と呼ばれます。これは、バイセクショ ンまたはトラバーサルによって行うことができます。探索の時間複雑度はO(n)と高すぎます。

var search = function(nums,target){
 let left = 0;
 let right = nums.length;
 //左閉じ右開きの区間を使う
 while(left < right){
 let mid = left + Math.floor((right - left)/2);
 if(nums[mid] === target){//等しい場合、右の境界を縮める
 right = mid;
 }else if(nums[mid] < target){// target > nums[mid], +1
 left = mid + 1;
 }else if(nums[mid] > target){ // target < nums[mid],右の境界を縮小する
 right = mid;
 };
 }
 return left;
}

右境界検索

左閉右開の使用は同じで、他の場所の理由は簡単で、主な戻り値と異なります。左閉右開区間であり、全体が左の区間で収縮しているので、値を見つけるために、左側の左と右になるので、1を減らすために。

var right_bound = function(nums, target) {
 if(nums.length === 0) return -1;
 let left = 0,right = nums.length;
 //左閉じ右開きの区間を使う
 while(left < right){
 let mid = Math.floor((left + right) / 2);
 if(nums[mid] === target){
 left = mid + 1; //等しい場合、左の境界を縮める
 }else if(nums[mid] < target){
 left = mid + 1; //target nums[mid]左境界を縮小する
 }else if(nums[mid] > target){
 right = mid; //target nums[mid],右の境界を縮小する
 }
 };
 return left - 1;//右の境界に戻る
}

変形例：回転した配列から値を検索

基本的にはバイナリのルックアップですが、回転した配列のセグメントが大きいか小さいかという問題があるので、中点の値がどのセグメントにあるかという余計なステップが必要になります。

var search = function(nums, target) {
 let start = 0; let end = nums.length - 1;
 while(start <= end){ //基本的なバイナリサーチ
 let mid = start + Math.floor((end - start)/2);
 if(nums[mid] === target) return mid; //検索結果は以下を返す
 if(nums[start] <=nums[mid]){ //中点の値は大きなセグメントにある
 if(target >= nums[start] && target < nums[mid]){
 end = mid - 1;
 }else {
 start = mid + 1;
 }
 }
 else if(nums[start] > nums[mid]){ //中点の値は小さいセグメントにある
 if(target > nums[mid] && target <= nums[end]){
 start = mid + 1;
 }else {
 end = mid - 1;
 }
 }
 }
 return -1;
};

変形例：回転した配列中の値を検索 II

元の質問 by leetcode: 回転ソートされた配列の検索 II

この質問は前の質問の変形で、重複する数字が追加されているため、セグメントのサイズを決定する際に <= を使用することはできません。の場合は特別な方法で処理する必要があります。

var search = function(nums, target) {
 let start = 0 ;
 let end = nums.length - 1;
 while(start <= end){
 let mid = start + Math.floor((end - start)/2);
 if(target === nums[mid]) return true;
 if(nums[start] < nums[mid]){
 if(target >= nums[start] && target < nums[mid]){
 end = mid - 1;
 }else{
 start = mid + 1;
 }
 }else if (nums[start] > nums[mid]){
 if(target> nums[mid] && target <= nums[end] ){
 start = mid + 1;
 }else {
 end = mid - 1;
 }
 }else if(nums[start] === nums[mid]){ //と等しい場合、求める値は区間の内側だけでなければならないので、内側に縮める。
 start++;
 };
 };
 return false;
};