Binary search

Binary search 有好幾種情況，以下根據不同的情況提供相應的解法。

當然這裡有個前提，就是陣列中的元素是已經排序好的。

Binary search 有好幾中情況:

1. 找到目標值
2. 找到最後一個小於或等於目標值的元素(upper bound)
3. 找到第一個大於或等於目標值的元素(lower bound)
4. 找到第一個大於目標值的元素(upper bound + 1)
5. 找到最後一個小於目標值的元素(lower bound - 1)
6. 找到第一個等於目標值的元素(lower bound + 等於)
7. 找到最後一個等於目標值的元素(upper bound + 等於)
8. 找到第一個小於目標值的元素(沒有意義)
9. 找到最後一個大於目標值的元素(沒有意義)

扣除第一種，其他八種情況代表是三個條件的組合:

1. 包不包含目標值
2. 找到的是第一個還是最後一個
3. 找到的是大於還是小於

1. Find exact value 找到目標值

只要找到目標值，就返回它的索引。沒有找到，就返回 -1。在這個情況中，元素不會重複出現。

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

2. Find the last element that is less than or equal to the target 找到最後一個小於或等於目標值的元素(upper bound)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] <= target) {
      result = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}

3. Find the first element that is greater than or equal to the target 找到第一個大於或等於目標值的元素(lower bound)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] >= target) {
      result = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }

  return result
}

4. Find the first element that is greater than the target 找到第一個大於目標值的元素(upper bound + 1)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] > target) {
      result = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }

  return result
}

5. Find the last element that is less than the target 找到最後一個小於目標值的元素(lower bound - 1)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] < target) {
      result = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}

6. Find the first element that is equal to the target 找到第一個等於目標值的元素(lower bound + 等於)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) {
      result = mid
      right = mid - 1
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}

7. Find the last element that is equal to the target 找到最後一個等於目標值的元素(upper bound + 等於)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) {
      result = mid
      left = mid + 1
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}

最開始寫宿舍養貓(上)(中)的時候是純靠記憶在寫的，直到要寫下篇的時候我想起來當初有留下一些文字，找回了五年前的紀錄一看，事情比記憶中的模樣還來的不光彩。這不是我一個人的故事，主要的角色有五隻貓六個人，鮮少提到其他人是因為很多事情不確定、不記得、不知道該怎麼說，或許我就這樣寫出來，是對其他當事人的不尊重。

我應該是所有人裡面養貓意願最強烈的，但卻沒有好好的照顧他們造成室友困擾。記得最後跟小貓相處時的自己相當灰暗。記得最後是我在沒有處理的情況下放生。原本以為當初的只是沒有認真幫忙找領養的家庭而已，沒想到對話紀錄翻出來才發現，小花應該是有機會被送走的，會變成這樣是被人決定的。

大三之後有特別去玉泉校區附近的青旅找被送養走的學妹還有汪汪，但他們已經不叫這個名字了，當然也不再認識我，變成了普通的親人的貓，不過看到他們順利長大還是很值得高興。後來那家青旅換人經營，貓也一起離開。 千反田後來有影片傳回來，領養她的人貌似家境還不錯。

我沒有想起來任何有關小哀的消息。

那隻母貓不是第一次出現在宿舍，只是我一開始沒有認出來，但其實在大一的時候就見過了，她當時會待在宿舍門口的樓梯旁邊，一點都不怕生，我還特別幫她照過相。後來也是因為偶然翻到相片，才發現原來是曾經見過的貓。

寒假的時候我收到了不少訊息:

「貓也不是隨便哪個房間都想待，她們只認你們的房間，好幾次貓想回來」

「今天又下雪了」

「你幫我找到小花，我去看看情況，情況不好我就送人」

「你自己做事不果決阿」

「找不到」

「樓裡宿管上次看到小花的時候，皮包骨頭，母貓我上次看到了一次，也是很瘦很瘦」

「我已經找了好幾天了，還是找不到」

因為還沒有回學校，還能稍微騙一下自己。等到大二下開學，回到學校之後不管到哪裡都找不到，一點希望也沒有留下，我告訴自己是我害死的。

翠柏宿舍過了一條馬路之後是白沙宿舍，我買東西的時候如果不想走到比較遠的超市，通常就會去白沙宿舍底下的啟真便利店，那裏有許多野貓，他們都不怕人，但也不會讓人靠近，相比之下在翠柏的貓都很親人。2015年的三月的某一天，我從白沙的便利商店出來，在經過花圃的時候蹲了下來，看看會不會有一隻主動蹭上來，這時我看見其中一隻貓，一張臉有兩種顏色，爪上是白色的毛。

時間慢慢接近期末，等寒假來的時候寢室裡空無一人，沒有人能照顧貓，必須趕快幫他們找到領養人。我知道不能找跟我們一樣的學生，養不下去的，所以為了幫他們找到新的家，我應該去接觸一些本地社群，一些喜愛動物的人會聚集的地方。但我什麼都沒有做，我沒有去PO文，沒有去找人問，甚至連一點調查都沒有做。完全把送養這件事情交給Hiro Dai了，貓不是他說要養的，他也不是我的室友，但我卻讓他幫我找五隻貓的領養者，我唯一做的就是每天下課回寢室之後看著他們傻笑，坐在地上陪他們玩。

第一隻被領養的是千反田。我猜測是因為從照片上看起來，她是最白最漂亮的吧。我們趁著母貓不在的時候把小貓送出去，剛開始的時候大家都很高興，但事情很快的就開始出乎意料，因為母貓回來後發現自己的孩子少了一個，她叫的撕心裂肺，在我們寢室裡到處尋找，出了寢室也繼續嚎，到處找小孩。我直到這時候才感覺到心碎，而初衷也開始動搖。

第二梯次被領養的是學妹還有汪汪，他們是一起走的，領養的人是玉泉校區附近的青年旅社。這是個好消息，因為大三之後我會換到玉泉校區，那時候我還能去看他們兩個。對方在晚上的時候開著車來接，我們從樓長的眼前抱著貓走出去，雖然沒有直接讓她看到，但那個聲音根本藏不住，真的要感謝當時的樓長默許我們養貓。

第三次，也是最後一次有人來接手，送走的是小哀。為什麼是小哀? 我不知道。千反田漂亮，學妹同樣是白貓而且個性很好特別親人，汪汪毛色烏黑亮麗而且是唯一的公貓，他們都先被領養走了。剩下來的小哀是隻膽小的貓，毛色是灰黑色的，給人的感覺有點畏畏縮縮的，發育跟其他貓起來比較不好，在搶奶的時候會搶不過，有時候要我們幫她。而我取名的Hana，是所有小貓裡面最兇的，她是唯一會抓傷我的貓，如果能夠平安長大，應該是跟現在公司裡面的貓一樣派(台語)，但Hana是我到後來最喜歡的貓，她是一隻三色的玳瑁貓，左右兩邊的臉不一樣顏色，腳掌上有白色的毛，因為這白色的毛，她差一點就被命名為襪子，但我堅持叫她Hana(也不是每次都講日文，也常常叫她小花)，我覺得她是最可愛的，不懂為什麼別人在選的時候不先選她。

送養的過程經歷了三次，不管是我還是母貓，都充滿了煎熬。我心中不知道喪失了什麼東西，變得相當陰暗，這影響到了我和小貓相處的方式。感覺被奪走了什麼，所以對剩下來的控制慾更強，再加上我沒有承受住母貓的反應，想留一隻小貓來陪她，最後的決定是Hana不送了。這是個錯誤的決定嗎? 以我後悔的程度來說是的。當時不確定是天真，還是裝作沒看見，杭州的冬天怎麼可能適合小貓，怎麼可能適合一個被人養在溫室中的小貓。

在真的放寒假之前我們後悔了，想找了人接手養著等我們回來，但是後來的情況相當混亂，沒辦法確定發生了什麼事情，只記得在離開寢室前沒多久，我把Hana跟她媽關在門外。

過了一段時間之後我得知後來的情況，最後一個離開的室友說:「她們中間好幾次想回來」

找到了當時的一些文字記錄，情況遠比我現在記得的要複雜，僅存的記憶還是過於美化當時的錯誤，只能說我比我記得的還差勁許多。今天先上本來預計周四要上的題目，「宿舍養貓」除了需要時間整理，更需要時間掙扎。

---

在公司內部除了我之外，還有另外三個同事會跟我搭同一路公車上下班，剛開始的時候我從來沒在車上遇到過他們，因為那時我可以說是這群人之中最早到的，同時也是最晚走的。也因為這樣，我曾經一度不知道還有另外兩個同事跟我上下班的路徑有重疊。

會那麼晚走的原因很單純，就是因為自己太菜了，不管是開發什麼東西都要做上半天，所以隨著我有點長進之後，時間慢慢變得比較正常。編程的功力長進的多少不知道，可以確定的是早一點下班的功力提升的很顯著，結果就是搭車的時候有時會遇其他同事，M看到我的時候會問:「你今天比較早?」。

工作一段時間之後RD的讀書會到了一個段落所以先暫停，我出門的時間就往後調整了一小時，上班的途中終於能碰見其他人。這段日子裡最常碰到的是M，由於之前不常遇到，一開始還會被特別問:「你今天比較晚?」。第二常碰到的是N，N總是能滔滔不絕的講，我時常感覺自己插不上話。那C呢? 我真的很少單獨遇到他，上下班各一次而已，上班的那一次我在車上的時候還沒認出來，因為他戴著口罩。

幾個月過去之後情況再次不同，M開始比較早進公司(絕對不是我晚了)，上班的車上最容易遇到的同事換成了N，偶爾碰到M的時候問出:「你今天比較晚?」的人則變成是我。不僅如此，M還因為工作愈發忙碌，下班時間開始往後延，而我則相反，雖然我也感覺自己變忙了，但離開公司的時間反而比之前又早了一些。M晚走到我後來就沒有在下班的時候遇過他，只能趁著早上的偶遇問:「我們上下班時間是不是黃金交叉?」

宿舍當然不能養貓。

其實一開始的時候就只是想投食還有跟貓玩，並沒有想要在寢室裡面養貓，是什麼時候有這種念頭? 是在發現母貓懷孕之後。那是大二上學期中，接著就要寒假了，而杭州的冬天是會下雪的，剛出生的小貓會活得下去嗎? 我心中的答案是傾向於他們活不去。而雖然過程中有分歧，但寢室內的大家最後還是決定收留這些貓，在最難熬的冬天來臨之前幫他們找到收養的人家。

宿舍不能養貓，理論上我們只能偷偷養，但我們寢室一直都養得很光明正大，大概是仗著那時候的樓長很喜歡我們，而且那時候有 Hiro Dai 在後面幫忙說話吧。為了這群貓，我們買了貓砂盆，買了飼料，手巧的王姓室友還用紙箱做了一個餵食槽。

小貓真的很可愛，我喜歡坐在地上跟他們玩，讓他們在我身上爬來爬去，有時候坐在椅子上，小貓也會順著褲管爬上來，然後睡在我腳上。熬夜的時候我就把小貓抱到書桌上，讓他們陪我玩電腦、陪我寫作業、陪我發呆。冬天因為太冷，常常會窩在床上，這時候我也會抱起一兩隻喵仔，跟我一起爬到書桌上放的床，他們會在床尾嬉鬧，我就在那邊看他們玩。早上起床的時候則是會特別小心，從床上爬下來的時候不能踩到他們，我還記得第一天他們可以自己翻出紙箱，第一天能夠從床上沿著樓梯上跳下去，那個學期我生活的重心就是這群小貓，我還曾經帶他們出去兜風，方法是把小貓 放在外套的內袋，那邊才足夠溫暖。

那時的我還有個很惡趣味的活動，小貓每次要進行一段比較長的跳躍時，都會準備很久，我會看準時機在他們還在空中的時候接住，然後放回去原本的起跳點，他們就會再跳一次，然後我就再接住一次，再放回去，樂此不疲。

母貓只有剛開始的時候才天天待在寢室裡，到了小貓可以自由活動之後反而不太常在寢室，只有偶爾才會回來餵奶，她想離開的時候會去抓門，我們就知道要放他離開。她想進來的時候會在寢室外面叫，有時候很時間還很早，我會幫她開門之後再躺回去睡。我特別喜歡那段時間，因為之前的大一過得很痛苦又很沒有意義，很多事情都沒有留下任何記憶，大二的這群貓給我的大學生活帶入了豐富的色彩，我好不容易認為大學生活是很快樂的。

原本是因為很美好的初衷收留了他們，也度過了一段很愉快的日子，然而隨著時間慢慢過去，領養的問題也開始浮現。我認為當初的自己責任要比別人還要多一些，因為一開始室友們對於要不要收留這群貓是有分歧的，而我是立場非常強烈的收留派，我理應花更多的心力跟時間去處理這件事情。

但是我沒有。